Priority Queues
Priority Queues are abstract data types where elements are dequeued according to their priority, not just their insertion order.
Priority vs Insertion Order
While standard queues operate on a strict First-In-First-Out basis, a Priority Queue assigns a 'priority' to each element. When an element is removed, the one with the highest priority (or lowest value in a min-queue) is extracted. This makes it perfect for scheduling tasks, managing bandwidth, or simulating events.
Binary Heap Backend
The most common and efficient way to implement a priority queue is using a Binary Heap. Arrays allow us to store this binary tree densely, utilizing simple arithmetic to navigate from a parent to its children. This avoids the overhead of managing node objects and pointers.
Terms, operations, and practical uses
Core Concepts
- Heap PropertyThe invariant stating that a parent node is always ordered before (or equal to) its children, depending on if it is a min-heap or max-heap.
- Complete Binary TreeA tree where every level is fully populated except possibly the last level, which is filled from left to right.
- Sift-Up / SwimThe operation of moving a newly inserted element up the tree until the heap property is restored.
Heap Operations
- Sift-Down / SinkThe operation of moving the root element down the tree (swapping with the smaller/larger child) until the heap property is restored.
- HeapifyThe O(N) process of converting an arbitrary array into a valid heap by performing sift-down operations on all non-leaf nodes from bottom to top.
- Extract-MinRemoving and returning the root element of a min-heap, followed by replacing it with the last element and sifting down.
Applications
- Dijkstra's AlgorithmUses a priority queue to always process the nearest unvisited vertex next, guaranteeing the shortest path.
- Huffman CodingRepeatedly extracts the two lowest-frequency trees from a priority queue to build an optimal prefix code tree.
- Kth Largest ElementMaintaining a min-heap of size K while iterating through N elements guarantees the root is the Kth largest element in O(N log K) time.
Build a min-priority queue
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
def push(self, val):
heapq.heappush(self.heap, val)
def pop(self):
return heapq.heappop(self.heap)
pq = PriorityQueue()
for value in (10, 5, 1):
pq.push(value)
print('Heap array:', pq.heap)#include <queue>
#include <vector>
class PriorityQueue {
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
public:
void push(int val) { pq.push(val); }
int pop() {
int val = pq.top(); pq.pop();
return val;
}
};import java.util.PriorityQueue;
class PQ {
PriorityQueue<Integer> pq = new PriorityQueue<>();
public void push(int val) { pq.offer(val); }
public int pop() { return pq.poll(); }
}insert 10, then 5, then 1Heap array: [1, 10, 5]Run the example step by step
Sifting Up and Down
When an element is inserted at the end of the heap array, it might violate the heap property. The 'sift-up' operation bubbles this element up the tree until it settles. Conversely, extracting the root replaces it with the last element, which is then 'sifted-down' to its correct position.
Applications
Priority queues are foundational for many advanced algorithms. They are the engine behind Dijkstra's Shortest Path algorithm, Prim's Minimum Spanning Tree algorithm, and Huffman Coding for data compression. They are also heavily used in operating system schedulers.