Binary Heaps & Priority Queues

A binary heap is a complete binary tree that satisfies the heap property: every parent is ≥ its children (max-heap) or ≤ its children (min-heap), so the root is always the extreme element. That partial order is exactly what a priority queue needs — O(1) access to the most extreme element with O(log n) insert and extract.

• Complete: every level is full except possibly the last, filled left to right — the property that enables the pointer-free array representation.
• Max-heap: every parent ≥ its children — the root is the maximum.
• Min-heap: every parent ≤ its children — the root is the minimum.

Array Representation

A complete binary tree maps 1:1 onto an array with no pointers. For a node at index i (0-based): left child 2i + 1, right child 2i + 2, parent floor((i − 1) / 2).

       15
      /  \
     10    8
    /  \   /
   7    4  3

array: [15, 10, 8, 7, 4, 3]
       idx  0   1  2  3  4  5

Parent/child hops are multiplications, not pointer dereferences — a heap of a million elements is a million contiguous ints, which gives excellent cache behavior.

Core Operations

Sift-Up and Sift-Down

Sift-up runs after an insert: append the element, then bubble it upward while it beats its parent. Sift-down runs after an extract: move the last element to the root, then bubble it downward, swapping with the better of its two children at each step. Both touch a single root-to-leaf path, hence O(log n).

Build-Heap Is O(n) — Not O(n log n)

Inserting n elements one at a time costs O(n log n). Floyd’s build is linear by sifting down from the last non-leaf node to the root:

for i from (n/2 − 1) down to 0:
    siftDown(i)

Most nodes live in the bottom levels, where sift-down travels only a short distance; summing height × count over all levels telescopes to O(n). A classic, non-obvious result.

Heap vs Sorted Array vs Balanced BST

If you only ever need the extreme element plus inserts, use a heap. Need search, ranges, or arbitrary deletion? The heap’s O(n) key lookup pushes you toward a BST.

Applications

• Dijkstra’s algorithm — a min-heap extracts the vertex with the smallest tentative distance, giving O((V + E) log V).
• Huffman coding — repeatedly extract the two smallest frequencies.
• Top-k streaming — keep a min-heap of size k; any element larger than the root replaces it.
• Task scheduling — a CPU scheduler extracts the highest-priority ready process.
• Median maintenance — a max-heap for the low half, a min-heap for the high half.

Heap Sort

1. Build a max-heap from the array — O(n).
2. Repeatedly swap the root (the max) with the last unsorted element, shrink the heap by 1, and sift-down the new root.
3. The tail fills with descending maxima — the array ends sorted ascending.

In-place, not stable, O(n log n) worst case — the workhorse of many systems’ sort when stability isn’t required.

Worked Example

Extract-min from the min-heap [2, 5, 8, 9, 7, 12]:

Step 1: 2 is the min. Move the last element to the root: [12, 5, 8, 9, 7]
Step 2: siftDown(0): 12 vs children 5, 8 → swap with 5:    [5, 12, 8, 9, 7]
Step 3: siftDown(1): 12 vs children 9, 7 → swap with 7:    [5, 7, 8, 9, 12]
Step 4: 12 is a leaf. Heap property restored.
Extracted min: 2. Result: [5, 7, 8, 9, 12]

Practice Trajectory

1. Implement a binary min-heap over an array (insert, extractMin, peek) and verify the index math on a 7-element tree.
2. Prove Floyd’s build is linear: instrument sift-down and count swaps on arrays of 100 and 1000 elements.
3. Implement heap sort and confirm it sorts but is not stable using (value, insertionOrder) records.
4. Solve “k largest elements in a stream” with a size-k min-heap and again with a sorted array; compare running times.
5. Trace Dijkstra on the Shortest Path topic’s graph with a min-heap and note when each vertex is finalized.

When It’s the Right Tool