Heaps and Priority Queues
A heap is a special tree where the value at every node is smaller than (or larger than) its children. The root always holds the smallest value (min-heap) or the largest (max-heap). This invariant lets you find the extreme value in O(1) and remove it in O(log n).
Why Not Just Sort?
If you just need the smallest value once, sorting is fine. But if you keep adding new items and pulling out the smallest, sorting again every time is wasteful. A heap maintains "smallest at the top" continuously, with O(log n) per operation. That's the magic.
Min-Heap vs Max-Heap
The only difference is the comparison rule:
- Min-heap: parent <= children. Root is the smallest.
- Max-heap: parent >= children. Root is the largest.
A heap is usually stored in an array, not as a node-and-pointer tree. For a node at index i, its children sit at 2i+1 and 2i+2, and its parent at (i-1)/2. This makes heaps cache-friendly and fast.
Sift Up and Sift Down
The heap maintains its property using two operations:
- Sift up: after inserting at the end, swap with parent while smaller, until the heap property holds
- Sift down: after removing the root and moving the last element to the top, swap with the smaller child while it's smaller, until the heap property holds
Both walk at most the tree's height, which is O(log n).
Priority Queue Uses
A priority queue is the abstract data type backed by a heap. It's used everywhere:
- Dijkstra's algorithm for shortest paths picks the next-closest node
- A* search picks the most promising path
- Task schedulers run the highest-priority job next
- Top-K queries keep only the K largest values seen so far
- Event simulators process events in time order
Try It Yourself
- Use a heap to find the K smallest values in a stream of numbers
- Implement a max-heap by negating values into a min-heap
- Build a "task scheduler" that processes tasks in priority order