Algorithms from zero
Priority queues
You have a heap. Now you wrap it in a new name and a promise: “You never search for the max or min. You always get it in one operation—the most urgent, highest-priority, smallest-cost thing first.” That promise is a priority queue—not a data structure (that is the heap underneath), but a contract that says what you can do. The heap is one way to keep that contract. Dijkstra’s algorithm uses it. Schedulers use it. Any time you must always process the most important thing next, you reach for a priority queue.
After this lesson you can explain the difference between an abstract data type and an implementation. You can state the priority queue interface: insert a new element, extractMin (or extractMax) to remove and return the highest-priority element, and peek to see it without removing. You understand that a binary heap is the standard implementation and why (O(log n) insert and extract, O(1) peek). You can recognize when a problem calls for a priority queue instead of a regular queue or array, and name three real-world uses: task scheduling, Dijkstra’s shortest path, and event simulation.
What is a priority queue?
A priority queue is an abstract data type—a contract, not a concrete data structure. It describes what you can do, not how it is built.
The contract says: you have a collection of elements, each with a priority (a number, or a comparison rule). You can:
- Insert a new element.
- ExtractMin (or extractMax): remove and return the element with the smallest (or largest) priority.
- Peek: look at the highest-priority element without removing it.
That is the interface. The heap lives underneath.
ADT vs. Implementation
An abstract data type (ADT) is a specification—a contract. It says what operations are supported and what they do. It does NOT say how.
A priority queue is an ADT. Its operations are insert, extractMin, and peek.
An implementation is the code. A binary heap is one common implementation: it uses a complete binary tree stored in an array, with the min-heap property (every parent ≤ children).
The same ADT can have many implementations. A priority queue could be:
- A binary heap (fast insert and extract, memory efficient).
- A sorted array (fast peek, slow insert and extract).
- A linked list (slow everything).
- A balanced BST like a red-black tree (log n for all operations, but larger constants).
When you code, you use the ADT abstraction. You ask: insert, extractMin, peek. The implementation is pluggable—swap it out, the client code does not change.
Why binary heap?
The binary heap is the standard implementation because it is fast (O(log n) insert and extract, O(1) peek) and memory efficient (no pointers, just an array). It is simple enough to code by hand, yet battle-tested.
Min-heap vs. Max-heap
In a min-heap, extractMin returns the smallest element. Used when you want to process the smallest cost, shortest time, or least urgent task first.
In a max-heap, extractMax returns the largest element. Used when you want the highest priority, greatest weight, or most urgent task first.
The logic is symmetric—if you need a max-heap and only have a min-heap library, negate the priorities and use min-heap.
The priority queue interface in pseudocode
PriorityQueue:
insert(element, priority)
Add element to the queue.
extractMin()
Remove and return the element with the smallest priority.
peek()
Return (without removing) the smallest-priority element.
isEmpty()
True if the queue is empty.
size()
Number of elements in the queue.Example: task scheduling
You have a task queue. Each task has a priority (1 = urgent, 10 = low priority). Tasks arrive at random times. You want to always work on the most urgent task next.
Queue: [print job (priority 3), compile (priority 5), test (priority 1)]
extractMin() → test with priority 1 (even though it was added last)
insert(deploy, priority 2)
Queue: [deploy (priority 2), print job (priority 3), compile (priority 5)]
extractMin() → deploy with priority 2A regular queue (FIFO) would not work here—it would force you to do print job first, then compile, wasting time on low-priority work.
Priority queue interface in code
1
class MinPriorityQueue {
2
constructor() {
3
this.heap = [];
4
}
5
6
// Insert element with a value (lower = higher priority)
7
insert(element, value) {
8
this.heap.push({ element, value });
9
this.siftUp(this.heap.length - 1);
10
}
11
12
// Remove and return the element with the smallest value
13
extractMin() {
14
const root = this.heap[0];
15
this.heap[0] = this.heap[this.heap.length - 1];
16
this.heap.pop();
17
if (this.heap.length > 0) {
18
this.siftDown(0);
19
}
20
return root.element;
21
}
22
23
// Peek at the smallest-value element without removing
24
peek() {
25
return this.heap.length > 0 ? this.heap[0].element : null;
26
}
27
28
// Check if empty
29
isEmpty() {
30
return this.heap.length === 0;
31
}
32
33
// Number of elements
34
size() {
35
return this.heap.length;
36
}
37
38
// Sift-up to restore heap property after insertion
39
siftUp(index) {
40
while (index > 0) {
41
const parentIndex = Math.floor((index - 1) / 2);
42
if (this.heap[index].value < this.heap[parentIndex].value) {
43
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
44
index = parentIndex;
45
} else {
46
break;
47
}
48
}
49
}
50
51
// Sift-down to restore heap property after removal
52
siftDown(index) {
53
while (true) {
54
const left = 2 * index + 1;
55
const right = 2 * index + 2;
56
let smallest = index;
57
58
if (left < this.heap.length && this.heap[left].value < this.heap[smallest].value) {
59
smallest = left;
60
}
61
if (right < this.heap.length && this.heap[right].value < this.heap[smallest].value) {
62
smallest = right;
63
}
64
65
if (smallest !== index) {
66
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
67
index = smallest;
68
} else {
69
break;
70
}
71
}
72
}
73
}
- L1 MinPriorityQueue wraps a heap array.
- L5 Insert an element with a priority value. Lower value = higher priority.
- L9 extractMin removes and returns the smallest-value element (the root of the min-heap).
- L17 peek returns the smallest-value element without removing it.
- L29 siftUp restores the heap property after insertion, moving the element upward.
- L39 siftDown restores the heap property after removal, moving the element downward.
Using the priority queue
1
const pq = new MinPriorityQueue();
2
pq.insert('task1', 5);
3
pq.insert('task2', 2);
4
pq.insert('task3', 1);
1
const pq = new MinPriorityQueue();
2
// After inserts: heap has [(task3,1), (task1,5), (task2,2)]
3
const extracted = pq.extractMin();
Priority queue operations using a binary heap
Insert: Appends a new element and calls sift-up. Sift-up moves the element upward one level per swap, and a heap with n elements has height O(log n).
- Time: O(log n)
ExtractMin: Removes the root, moves the last element to the root, and calls sift-down. Sift-down also takes O(log n).
- Time: O(log n)
Peek: Returns the root in one array access.
- Time: O(1)
IsEmpty and size: Check the array length.
- Time: O(1)
Why not other implementations?
A sorted array could give you O(1) peek, but insert and extract would require shifting O(n) elements—O(n) per operation.
An unsorted array gives you O(1) insert, but extractMin requires scanning all elements to find the smallest—O(n) per operation.
A linked list is O(n) for everything.
A binary heap balances all three: O(log n) insert and extract, O(1) peek. This is why it is the standard choice for priority queues.
Space complexity
The heap uses a single array, so space is O(n) for n elements.
In a priority queue based on a binary min-heap, which operation is guaranteed to be O(1)?
You are building a task scheduler. Tasks have priorities (lower number = more urgent). You want to always execute the most urgent task next. What should you use?
What is the difference between an abstract data type (ADT) and an implementation?
In Dijkstra's shortest path algorithm, you need to repeatedly extract the vertex with the smallest distance. Which data structure is this?
A min-heap priority queue has 8 elements. How many steps (comparisons and swaps) does extractMin take in the worst case?
You need to merge 4 sorted lists into one sorted list. Which approach uses a priority queue?
lesson.inset.undefined
Why priority queues matter. Any real system with tasks, events, or requests has priorities. A web server has requests from users; some are more important (paying customers first). A robot has sensors and actuators; urgent safety events take priority. A hospital has patients in a waiting room; critical cases are seen first. Without a priority queue, you either process things randomly (unfair, inefficient) or manually search for the most important thing (slow, O(n)). A priority queue solves both problems: always give me the most important thing, fast.
lesson.inset.undefined
Confusing the ADT and the implementation. A priority queue is NOT a heap. A heap is one way to implement a priority queue. If someone asks “Is a priority queue a heap?”, the answer is “No, a priority queue is an ADT; a heap is an implementation of that ADT.” This distinction matters because in an interview you might say “I will use a priority queue backed by a heap” to make clear you are thinking about both levels.
lesson.inset.undefined
Decreasing a priority. Some priority queue problems (like Dijkstra) need to lower an element’s priority after insertion. A binary heap does not support this directly—you would need to rebuild or use a more complex implementation (Fibonacci heap, or re-insert with the new priority and skip the old one). For this lesson, we assume a simple priority queue that supports insert, extractMin, and peek only.
Explain the relationship between a priority queue (the ADT) and a binary heap (the implementation). What operations must the ADT support, and why is the heap a good choice?
A priority queue is an abstract data type—a contract that promises three operations: insert a new element, extractMin to remove and return the highest-priority element, and peek to see the highest-priority element without removing. A binary heap is the standard implementation, giving O(log n) insert and extract, O(1) peek. Understand the difference: the ADT is the interface; the implementation is the code. A priority queue is not a FIFO queue or a LIFO stack—it always gives you the most important thing next. Use a priority queue whenever you must always process the most urgent element: task scheduling, Dijkstra’s shortest path, event simulation, merging sorted streams. Next: Unit 08, lesson 04 applies the priority queue to top-K problems, and lesson 05 shows k-way merge.