DSA Notes
Understand the Priority Queue abstract data type, implement it with a binary heap, and explore real-world applications from task scheduling to graph algorithms.
The Abstract Data Type
A priority queue is an abstract data type (ADT) where each element has a priority, and elements are served in priority order rather than insertion order. Unlike a regular queue (FIFO), a priority queue always dequeues the element with the highest priority first.
The key operations are:
- insert(element, priority): Add an element with a given priority
- extract_max() / extract_min(): Remove and return the highest/lowest priority element
- peek(): View the top-priority element without removing it
- change_priority(element, new_priority): Update an element's priority
Think of an emergency room: patients are not treated in arrival order — the person having a heart attack gets seen before someone with a sprained ankle, regardless of who arrived first.
Why Not Just Sort?
A naive approach would be to keep a sorted array and pop from the end. But inserting into a sorted array takes O(n) due to shifting. A linked list gives O(n) insertion for finding the right spot. Neither is ideal when you have frequent insertions AND extractions.
| Implementation | Insert | Extract | Peek |
|---|---|---|---|
| Unsorted Array | O(1) | O(n) | O(n) |
| Sorted Array | O(n) | O(1) | O(1) |
| Binary Heap | O(log n) | O(log n) | O(1) |
| Fibonacci Heap | O(1) amortized | O(log n) amortized | O(1) |
The binary heap gives us the best balance for general use: O(log n) for both insert and extract, with very low constant factors and excellent cache performance (array-based, no pointer chasing).
Implementation: Min-Priority Queue
Why the Counter Tiebreaker?
When two items have equal priority, we need a stable comparison. Without the counter, Python would try to compare the items themselves, which fails for objects that do not support <. The counter ensures FIFO ordering among equal priorities.
Using Python's heapq
In practice, you rarely implement from scratch. Python's heapq module is a production-ready min-heap:
import heapq
pq = []
heapq.heappush(pq, (2, "medium task"))
heapq.heappush(pq, (1, "urgent task"))
heapq.heappush(pq, (3, "low priority task"))
while pq:
priority, task = heapq.heappop(pq)
print(f"Processing: {task} (priority {priority})")
# Output: urgent task, medium task, low priority taskFor a max-priority queue, negate the priorities:
heapq.heappush(pq, (-priority, task)) # Higher priority = more negative = pops firstApplication 1: Task Scheduling
Operating systems use priority queues to schedule processes. Each process has a priority level, and the CPU always runs the highest-priority ready process:
Application 2: Huffman Coding
Huffman's algorithm builds an optimal prefix code by repeatedly merging the two least-frequent symbols. A min-priority queue makes this clean:
Application 3: Dijkstra's Algorithm
As discussed in the min-heap article, Dijkstra's algorithm uses a priority queue to always process the vertex with the smallest tentative distance next. This greedy choice guarantees correctness for non-negative edge weights.
Application 4: Merge K Sorted Arrays
Given K sorted arrays, merge them into one sorted array. Push the first element of each array into a min-heap, then repeatedly extract the minimum and push the next element from that array:
Time: O(N log K) where N is total elements across all arrays.
Max-Priority Queue in C++
C++ STL provides priority_queue which is a max-heap by default:
#include <queue>
#include <vector>
// Max-priority queue (default)
std::priority_queue<int> maxPQ;
maxPQ.push(3);
maxPQ.push(1);
maxPQ.push(4);
maxPQ.top(); // 4
maxPQ.pop(); // removes 4
// Min-priority queue
std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;Key Takeaways
- A priority queue is an ADT — the heap is just one implementation (the best general-purpose one)
- Binary heaps give O(log n) insert/extract with minimal overhead
- Use a counter tiebreaker for stable ordering with equal priorities
- Real applications span from OS scheduling to compression to graph algorithms
- Python's
heapqis min-heap only — negate for max behavior
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Priority Queue using Heap.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, heaps, priority, queue
Related Data Structures & Algorithms Topics