The Hospital ER Analogy
In a hospital emergency room:
- Regular queue: First come, first served
- Priority queue: Most critical patients first, regardless of arrival
A patient with a heart attack gets treated before someone with a sprained ankle, even if the ankle arrived first.
Priority queues serve items by importance, not arrival order.
How It Works
The Core Operations
INSERT - Add item with a priority
PQ: [(B, 3), (A, 5)] (item, priority)
insert(C, 1)
PQ: [(C, 1), (B, 3), (A, 5)]
EXTRACT_MAX/MIN - Remove highest/lowest priority item
PQ: [(C, 1), (B, 3), (A, 5)] (min-heap)
extractMin() → returns C
PQ: [(B, 3), (A, 5)]
PEEK - Look at highest priority item
PQ: [(C, 1), (B, 3), (A, 5)]
peekMin() → C (doesn't remove)
Time Complexities
| Operation | Time |
|---|---|
| Insert | O(log n) |
| Extract | O(log n) |
| Peek | O(1) |
| Build from array | O(n) |
Min-Heap vs Max-Heap
Min-Heap (Priority = Lowest First)
Extract returns the SMALLEST value:
PQ: [1, 3, 5, 7, 9]
extractMin() → 1
Use for: Dijkstra (smallest distance), task scheduling (earliest deadline)
Max-Heap (Priority = Highest First)
Extract returns the LARGEST value:
PQ: [9, 7, 5, 3, 1]
extractMax() → 9
Use for: Top K elements, highest priority tasks
Most languages default to min-heap. For max-heap, negate values or use custom comparator.
Visual Walkthrough
Hospital ER Priority Queue (min = most urgent):
Patient arrives: Ankle (priority 5)
PQ: [(Ankle, 5)]
Patient arrives: Cold (priority 8)
PQ: [(Ankle, 5), (Cold, 8)]
Patient arrives: Heart Attack (priority 1)
PQ: [(Heart Attack, 1), (Ankle, 5), (Cold, 8)]
Doctor available:
extractMin() → Heart Attack (priority 1)
PQ: [(Ankle, 5), (Cold, 8)]
Doctor available:
extractMin() → Ankle (priority 5)
PQ: [(Cold, 8)]
Heart Attack was treated first despite arriving last!
Where Priority Queues Are Used
1. Dijkstra's Algorithm
Finding shortest paths in weighted graphs:
Typically process the node with the smallest known distance:
PQ: [(A, 0), (B, ∞), (C, ∞)]
extractMin() → A (distance 0)
Update neighbors, add back to PQ
extractMin() → whoever now has smallest distance
2. Task Scheduling
Operating system CPU scheduling:
Tasks with different priorities:
High priority (1): System processes
Medium priority (5): User applications
Low priority (9): Background jobs
PQ serves high priority tasks first.
3. Huffman Coding
Building optimal compression trees:
Repeatedly combine the two smallest frequencies:
PQ: [(a:5), (b:9), (c:12), (d:13)]
Extract two smallest: a(5), b(9)
Combine: (ab:14)
Insert back: PQ: [(c:12), (d:13), (ab:14)]
Repeat...
4. K Largest/Smallest Elements
Find top K elements from a stream:
For K largest: Use min-heap of size K
If new element > heap top: replace
For K smallest: Use max-heap of size K
If new element < heap top: replace
Only O(n log K) instead of O(n log n) for full sort!
5. Merge K Sorted Lists
K sorted lists:
List 1: [1, 4, 7]
List 2: [2, 5, 8]
List 3: [3, 6, 9]
PQ holds one element from each list:
PQ: [(1, list1), (2, list2), (3, list3)]
extractMin() → 1
Add next from list1: PQ: [(2, list2), (3, list3), (4, list1)]
Repeat to get merged: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Implementation: The Heap
Priority queues are typically implemented using a heap:
Heap structure (array representation):
[1, 3, 5, 7, 9, 11, 13]
As a tree:
1
/ \
3 5
/ \ / \
7 9 11 13
Parent of i: (i-1) / 2
Left child of i: 2i + 1
Right child of i: 2i + 2
Heap property: Parent ≤ children (min-heap) or Parent ≥ children (max-heap).
Classic Problems
1. Kth Largest Element
Array: [3, 2, 1, 5, 6, 4], k = 2
Use min-heap of size k:
Process 3: heap = [3]
Process 2: heap = [2, 3]
Process 1: 1 < 2, skip
Process 5: 5 > 2, replace → heap = [3, 5]
Process 6: 6 > 3, replace → heap = [5, 6]
Process 4: 4 < 5, skip
Top of heap = 5 = 2nd largest ✓
2. Meeting Rooms II
Find minimum meeting rooms needed:
Meetings: [(0,30), (5,10), (15,20)]
Sort by start time, use min-heap for end times:
Start 0: heap = [30] 1 room
Start 5: 5 < 30, need new room
heap = [10, 30] 2 rooms
Start 15: 15 > 10, reuse room
heap = [20, 30] still 2 rooms
Answer: 2 rooms
3. Find Median from Data Stream
Use two heaps:
Max-heap: smaller half
Min-heap: larger half
Stream: 1, 2, 3
Add 1: max = [1], min = []
Add 2: max = [1], min = [2]
Median = (1 + 2) / 2 = 1.5
Add 3: max = [1, 2], min = [3]
Median = 2
Priority Queue vs Sorted Array
| Operation | Priority Queue | Sorted Array |
|---|---|---|
| Insert | O(log n) | O(n) |
| Get min/max | O(1) | O(1) |
| Extract min/max | O(log n) | O(1) or O(n) |
| Search | O(n) | O(log n) |
Priority queue wins when you need frequent inserts with extracts.
Common Mistakes
1. Wrong Heap Type
Need largest first? Use max-heap. Need smallest first? Use min-heap.
2. Not Understanding Negate Trick
Most libraries are min-heap. For max-heap, negate values: Insert -x, extract gives smallest (-largest), negate result.
3. Forgetting to Add Back
After processing an item (like in Dijkstra), you often add new items back!
FAQ
Q: Priority queue vs regular queue?
Regular queue: FIFO (first in, first out). Priority queue: Highest priority out first.
Q: Is priority queue a heap?
A heap is the most common implementation. Priority queue is the abstract concept.
Q: When to use priority queue vs sorting?
Use priority queue when data arrives over time (stream). Use sorting when you have all data upfront.
Q: Min-heap or max-heap by default?
Most languages use min-heap. Check your language's documentation!
Summary
A priority queue serves items by priority, not arrival order.
Key Takeaways:
- Insert: O(log n), Extract: O(log n), Peek: O(1)
- Min-heap: smallest first; Max-heap: largest first
- Implemented using a heap (array-based tree)
- Used in: Dijkstra, scheduling, top K, merging
- Not FIFO - priority determines order
- Essential for greedy algorithms
Priority queues enable efficient "get the current best" operations!
Related Concepts
Leave a Comment
Comments (0)
Be the first to comment on this concept.
Comments are approved automatically.