Binary heaps
A binary heap is a complete binary tree with a simple ordering rule. Stored in an array, it is the standard way to implement a priority queue.
The heap property
In a min-heap, every node's key is less than or equal to its children's keys, so the minimum is always at the root. A max-heap reverses this. Unlike a BST, there is no ordering between siblings or between left and right subtrees; the heap is only partially ordered, which makes it cheaper to maintain.
Shape and array storage
A heap is a complete binary tree: every level is full except possibly the last, which fills from the left. So it fits perfectly in an array with no gaps: the root is at index 0, children of i at 2i + 1 and 2i + 2, and the parent of i at (i - 1) // 2. Its height is floor(log2 n), so it is always balanced.
Insertion: sift up
To insert, place the new key in the next free array slot, the bottom-left-most open position, keeping the tree complete. Then sift up: while it is smaller than its parent, swap them. At most one swap per level, so insertion is O(log n).
Extract-min: sift down
To remove the minimum, take the root, move the last element into the root position, and shrink the array. Then sift down: while the element is larger than its smaller child, swap with that child. This restores the heap property in O(log n). Peeking at the minimum without removing it is O(1).
Building a heap in linear time
Inserting n items one by one costs O(n log n). Floyd's bottom-up method is faster: put all items in the array, then sift down each non-leaf node from the last one, index n // 2 - 1, back to the root. Most nodes are near the bottom and sift only a short way, so the total cost is O(n).
Heapsort
Heapsort builds a max-heap in O(n), then repeatedly swaps the root, the largest item, with the last element of the heap, shrinks the heap by one, and sifts the new root down. After n - 1 steps the array is sorted ascending. It runs in O(n log n) worst case using O(1) extra space, though it is not stable and is usually slower than quicksort in practice because of poor cache behaviour.
Beyond binary heaps
Decrease-key, lowering an item's priority value, is useful in Dijkstra's algorithm; it needs a way to find the item's position, often a side map from item to index. d-ary heaps give each node d children, making trees shallower. Fibonacci heaps offer O(1) amortised decrease-key, which is theoretically faster for dense graphs, though rarely used because of large constant factors.
Worked example
Insert 5, 3, 8, 1 into an empty min-heap. [5]. Insert 3: [5, 3], 3 < 5 so swap: [3, 5]. Insert 8: [3, 5, 8], no swap. Insert 1 at index 3: parent index 1 holds 5, swap: [3, 1, 8, 5]; parent index 0 holds 3, swap: [1, 3, 8, 5]. Extract-min returns 1; move 5 to the root: [5, 3, 8]; 5 > smaller child 3, swap: [3, 5, 8].
Key takeaways
A min-heap keeps each parent no larger than its children, so the minimum is at the root; heaps are only partially ordered. As complete trees they live in arrays with children at 2i + 1 and 2i + 2, and height floor(log2 n). Insert by appending and sifting up; extract by moving the last element to the root and sifting down, both O(log n); peek is O(1). Floyd's method builds a heap in O(n). Heapsort sorts in O(n log n) with O(1) space but is unstable. Decrease-key needs position tracking; d-ary and Fibonacci heaps are variants.
Flashcard
Each parent at most its children
Check your understanding
In the min-heap array [2, 4, 3, 9, 7], which value moves to the root during extract-min, before sifting down?