712539. Implementation of Priority Queue using Binary Heap
Implementation of Priority Queue using Binary Heap
Summary
A priority queue is a data structure that allows you to store elements with associated priorities, where elements are extracted in order of their priorities. In this problem, we will implement a priority queue using a binary heap. The key concepts involved are binary heaps and priority queues.
Detailed Explanation
To implement a priority queue using a binary heap, we can follow these steps:
- Create a binary heap with the given elements as nodes.
- Define the parent-child relationship for each node in the heap.
- Implement an insertion function that inserts a new element into the heap while maintaining the heap property (i.e., the parent node is always greater than or equal to its child nodes).
- Implement a deletion function that removes and returns the root node of the heap, which represents the highest priority element.
Here's a step-by-step breakdown of the solution:
Insertion Function
To insert a new element into the heap, we first find the position where it should be inserted. We then swap the new element with its parent node until the heap property is maintained.
1. Find the position for insertion (i.e., the last leaf node)
2. Compare the new element with its parent node
- If the new element has a higher priority, swap the two elements
3. Repeat step 2 until the heap property is maintained
Deletion Function
To remove and return the root node of the heap (i.e., the highest priority element), we simply replace the root node with the last leaf node and then restore the heap property.
1. Replace the root node with the last leaf node
2. Compare the new root node with its child nodes
- If the child node has a higher priority, swap the two elements
3. Repeat step 2 until the heap property is maintained
4. Return the removed root node (i.e., the highest priority element)
Time complexity for both insertion and deletion functions is O(log n), where n is the number of nodes in the heap.
Space complexity is O(n), as we need to store all elements in the heap.
Optimized Solutions
Java
public class PriorityQueue {
private int[] array;
private int size;
public PriorityQueue(int capacity) {
array = new int[capacity + 1];
size = 0;
}
public void insert(int value) {
array[++size] = value;
heapifyUp(size);
}
public int remove() {
int value = array[1];
array[1] = array[size--];
heapifyDown(1);
return value;
}
private void heapifyUp(int index) {
while (index > 1 && array[parent(index)] < array[index]) {
swap(parent(index), index);
index = parent(index);
}
}
private void heapifyDown(int index) {
int left = leftChild(index);
int right = rightChild(index);
int largest = index;
if (left <= size && array[left] > array[largest]) {
largest = left;
}
if (right <= size && array[right] > array[largest]) {
largest = right;
}
if (largest != index) {
swap(index, largest);
heapifyDown(largest);
}
}
private int parent(int index) {
return index / 2;
}
private int leftChild(int index) {
return 2 * index;
}
private int rightChild(int index) {
return 2 * index + 1;
// Helper function to swap two elements in the array
private void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}