Heaps & Priority Queues
A binary heap is a complete binary tree that satisfies the heap property:
- Max-heap: Every parent node ≥ its children (root is the maximum).
- Min-heap: Every parent node ≤ its children (root is the minimum).
Heaps are typically implemented as arrays for cache efficiency.
Array Representation
For a node at index i (0-based):
- Left child:
2i + 1 - Right child:
2i + 2 - Parent:
floor((i − 1) / 2)
Core Operations
| Operation | Complexity | Description |
|---|---|---|
| Insert | O(log n) | Add element at end, sift-up |
| Extract (pop) | O(log n) | Remove root, replace with last, sift-down |
| Peek | O(1) | Return root without removal |
| Build (heapify) | O(n) | Sift-down from last non-leaf to root |
| Heap sort | O(n log n) | Extract repeatedly to produce sorted array |
Build Heap (Floyd’s Algorithm)
Building a heap from an unsorted array is O(n) — surprisingly faster than O(n log n). The trick: sift-down from the last non-leaf node to the root:
for i from n/2 − 1 down to 0:
siftDown(i)Applications
- Priority queues: Insert with priority, extract the highest-priority element.
- Dijkstra’s algorithm: Extract the vertex with smallest distance.
- Huffman coding: Build an optimal prefix code tree by repeatedly extracting the two smallest frequencies.
- Task scheduling: Schedule processes by priority (CPU scheduler).
- K largest/smallest elements: Keep a heap of size k while streaming data.
Heap Sort
- Build a max-heap from the array — O(n).
- Repeatedly swap the root (max) with the last element and sift-down the new root, reducing the heap size by 1 — O(n log n).
- Result: the array is sorted in ascending order.
Properties: In-place, not stable, O(n log n) worst-case.