Binary Heap

A binary heap is a complete binary tree stored compactly in an array, satisfying the heap property: every parent is less-than-or-equal-to (min-heap) or greater-than-or-equal-to (max-heap) its children. It supports peek() in O(1), insert() and extract-min/max() in O(log n), and (surprisingly) build() from an unsorted array in O(n). It’s the workhorse data structure behind priority queues, heap sort, and Dijkstra’s algorithm.

1. Intuition — The Tournament Bracket

Imagine a single-elimination basketball tournament with 8 teams.

• Teams play in pairs; the better team in each match advances.
• After three rounds, one team is in the final position — the champion.
• The bracket structure is a complete binary tree: every internal node is the winner of its two children.

A min-heap is the same idea, but with “smaller value” instead of “better team”:

• Every parent ≤ both children.
• The root is the smallest element in the entire heap (the “champion of small”).

The clever part: instead of using pointers (parent → left/right children), we store the tree flat in an array, exploiting the structure of a complete binary tree.

2. The Array Encoding (THE Key Idea)

For a 0-indexed array of size n:

• parent of index i = (i - 1) // 2
• left child of index i = 2*i + 1
• right child of index i = 2*i + 2

Visualizing:

index:    0
         / \
        1   2
       /\  /\
      3  4 5 6
     /\
    7  8

In array form: [0, 1, 2, 3, 4, 5, 6, 7, 8]. The tree shape is implicit in the index arithmetic.

Why a complete tree? A complete binary tree (every level full except possibly the last, which is filled left-to-right) has exactly n nodes mapped onto exactly n array slots — no holes, no wasted memory. The shape is enforced: if you have 7 elements, they occupy indices 0-6, period.

Some texts use 1-indexed arrays

CLRS uses 1-indexed for cleaner formulas: parent = i // 2, left = 2i, right = 2i + 1. We use 0-indexed here because Python’s heapq does. Be consistent within a single piece of code.

3. Tiny Worked Example — Min-Heap

Build a min-heap from [5, 2, 8, 1, 9, 3, 7].

After heapify (we’ll see how in §6), the heap is:

            1
           / \
          2   3
         /\  /\
        5  9 8 7

Array:  [1, 2, 3, 5, 9, 8, 7]

Verify the heap property:

• 1 ≤ 2 ✓, 1 ≤ 3 ✓
• 2 ≤ 5 ✓, 2 ≤ 9 ✓
• 3 ≤ 8 ✓, 3 ≤ 7 ✓

The root is the smallest. The order of non-root elements is not sorted — the heap is a partial order, not a total one. That’s the trade-off: weaker invariant = cheaper to maintain.

4. Operations

4.1 peek() — Look at the Top

def peek(heap): return heap[0]

O(1). The min (or max) is always at index 0.

4.2 insert(x) — Add an Element

1. Append x to the end of the array (preserves “complete tree” shape).
2. Sift up (a.k.a. percolate up, bubble up): while x is smaller than its parent, swap them.

sift_up(heap, i):
    while i > 0:
        parent := (i - 1) // 2
        if heap[i] < heap[parent]:
            swap heap[i], heap[parent]
            i := parent
        else:
            break

Worst case: x is the new minimum and bubbles all the way up to the root → O(log n) swaps (the tree’s height is ⌈log₂(n+1)⌉).

4.3 extract_min() — Remove and Return the Minimum

1. Save heap[0] as the result.
2. Move the last element to position 0 (preserves “complete tree” shape).
3. Sift down (a.k.a. heapify-down, bubble down): while it’s larger than the smaller of its children, swap with that child.

sift_down(heap, i):
    n := length(heap)
    while True:
        left  := 2*i + 1
        right := 2*i + 2
        smallest := i
        if left  < n and heap[left]  < heap[smallest]: smallest := left
        if right < n and heap[right] < heap[smallest]: smallest := right
        if smallest == i: break
        swap heap[i], heap[smallest]
        i := smallest

O(log n) — each iteration descends one level; the tree has O(log n) levels.

4.4 delete_arbitrary(i) — Remove Element at Index i

1. Replace heap[i] with heap[-1] (last element).
2. Pop the last element off the array.
3. Sift up or sift down from i (which one depends on whether the swapped-in value is smaller or larger than the original — try both, only one will move).

O(log n). Less commonly used than insert/extract.

4.5 change_priority(i, new_value)

Update heap[i] = new_value, then sift up or down. Used in Dijkstra’s Algorithm when we discover a shorter path to a vertex already in the heap. Most “production” priority queues handle this with a decrease_key operation.

Python's heapq doesn't support efficient decrease-key

CPython’s heapq is a basic binary heap with no built-in decrease-key. Common workaround: insert the new (better) priority and let the old entry expire (“lazy deletion”). For Dijkstra’s Algorithm, this works fine — pop and skip if the popped distance is stale.

5. Python — Using heapq

import heapq
 
# heapq is a MIN-heap. There is no max-heap variant; use negation.
heap = [5, 2, 8, 1, 9]
heapq.heapify(heap)              # in-place: O(n)
print(heap)                       # [1, 2, 8, 5, 9] — note: NOT sorted!
 
heapq.heappush(heap, 3)           # O(log n)
print(heapq.heappop(heap))        # 1 — O(log n)
 
# Top-3 smallest:
print(heapq.nsmallest(3, [5, 2, 8, 1, 9]))   # [1, 2, 5]
print(heapq.nlargest(3, [5, 2, 8, 1, 9]))    # [9, 8, 5]

Max-heap trick

# Insert -x, pop -x, negate again on read
heap = []
heapq.heappush(heap, -5)
heapq.heappush(heap, -2)
heapq.heappush(heap, -8)
print(-heapq.heappop(heap))      # 8 (biggest)

For tuple-based priorities (e.g., (priority, item)), use the natural tuple ordering:

heapq.heappush(heap, (3, "low priority task"))
heapq.heappush(heap, (1, "high priority task"))
print(heapq.heappop(heap))        # (1, 'high priority task')

If two priorities tie, Python compares the second tuple element, which can fail if items aren’t comparable. Common fix: use (priority, counter, item) with a monotonic counter to break ties.

6. Build-Heap in O(n) — The Surprising Result

Naive thinking: to build a heap from an unsorted array, insert each of n elements, each insert is O(log n) → total O(n log n).

Tighter analysis: if instead of n inserts you do n/2 sift-down calls bottom-up, total work is O(n). The trick is most nodes are near the bottom (and have very short sift paths), so the cumulative work is bounded.

def heapify(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):    # bottom-up over internal nodes
        sift_down(arr, i)

Why O(n)?

In a heap of size n:

• ~n/2 leaves: 0 work each
• ~n/4 nodes one level up: ≤ 1 sift-down step each
• ~n/8 nodes two levels up: ≤ 2 steps each
• …
• 1 root: ≤ log n steps

Total work = Σ_{k=0}^{log n} (n / 2^(k+1)) · k.

This sum equals n · Σ k/2^(k+1), and the infinite sum Σ k/2^k converges to 2. So total work is O(n). (See Big-O Notation §11 for the same argument from the complexity-analysis side.)

Insertion-by-insertion would not give O(n) — it gives O(n log n), because each insert is independently O(log n) (top-down).

7. Heap Sort

Sort an array using a heap:

def heap_sort(arr):
    heapify(arr)                         # O(n) — make it a min-heap
    sorted_out = []
    while arr:
        sorted_out.append(heapq.heappop(arr))   # O(log n) per extract
    return sorted_out

Total: O(n) + n · O(log n) = O(n log n). Worst-case guaranteed, unlike Quicksort.

In-place version (using max-heap): heapify into a max-heap, then repeatedly swap arr[0] with arr[n-1], decrement n, sift down — the largest “exits” to the back of the array. After n iterations, the array is sorted in ascending order.

Heap sort vs merge sort vs quicksort — see the comparison table in Quicksort §12. The TL;DR:

• Heap sort: O(n log n) guaranteed, in-place, but cache-unfriendly (heap accesses jump around). In practice, slower than quicksort by 2-3× on random data.
• Used as the fallback in Intro Sort (C++ std::sort) when quicksort recursion gets too deep.

8. Use Cases

8.1 Priority Queue

The canonical use. Whenever you need “give me the next-best element” repeatedly, use a heap.

• Task scheduler: tasks have priorities; pick the highest-priority next.
• Event simulation: events have timestamps; process in order.
• Operating system schedulers historically used heap-based priority queues.

8.2 Top-K Problems

“Find the K largest elements in an array of n” — use a min-heap of size K.

import heapq
def top_k(nums, k):
    return heapq.nlargest(k, nums)        # under the hood: O(n log k)

Why min-heap (not max)? You want to evict the smallest of your top-K when a bigger element comes in. The min is at heap[0], so checking + replacing is O(log k).

def top_k_manual(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heappushpop(heap, x)    # one operation, O(log k)
    return heap                            # contains top k, in heap order

O(n log k) — much better than O(n log n) from sorting the full array.

8.3 K-Way Merge

Merge k sorted lists into one sorted list:

def merge_k_sorted(lists):
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    out = []
    while heap:
        val, i, j = heapq.heappop(heap)
        out.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j+1], i, j+1))
    return out

O(N log k) where N = total elements. Used in external merge sort.

8.4 Dijkstra’s Algorithm

Shortest-path graph algorithm. Maintains a min-heap of (tentative_distance, node) and repeatedly extracts the closest unvisited node. Heap-based Dijkstra runs in O((V + E) log V).

8.5 Median Maintenance (Two Heaps Pattern)

Maintain a running median over a stream:

• Max-heap holds the lower half of seen elements.
• Min-heap holds the upper half.
• Median = top of one (if sizes differ) or average of both tops (if equal).

Each insert: O(log n). Each median query: O(1). Used in “Find Median from Data Stream” (LC 295).

8.6 Huffman Coding

Build an optimal prefix-free code by repeatedly extracting the two least-frequent symbols, merging them into a tree node with frequency = sum, reinserting. The heap drives the “greedy” choice.

9. When NOT to Use a Heap

• Sorted iteration of all elements — heap is partial order; you’d extract n elements, paying O(n log n). If you need full sorted order anyway, sort directly.
• Range queries / arbitrary lookup — heaps don’t support “find element x” or “find the k-th element” efficiently. Use a Binary Search Tree or Segment Tree.
• Updating a specific element — possible (change_priority) but requires maintaining a value → index map alongside the heap. Often easier with a sorted structure.
• Many small heaps — overhead might exceed simple sorting.

10. Pitfalls

10.1 Min-Heap vs Max-Heap Confusion

Always state which kind. “Heap” without qualifier defaults to min-heap in CS but max-heap in some textbooks (and in pseudocode for heap-sort, where max-heap is natural).

10.2 Insertion-Order Build is O(n log n), not O(n)

If you write for x in arr: heappush(heap, x), you’ve used O(n log n) time. Use heapify(arr) to get O(n).

10.3 Heap is Not Sorted

Printing a heap shows array order, which is not sorted. The heap property is local (parent vs children), not global. Don’t assume heap[1] ≤ heap[2].

10.4 Comparable Items

If you push (priority, item) tuples and two priorities tie, Python compares item. If items are dicts or other un-orderable types, you get a TypeError. Add a unique tiebreaker: (priority, counter, item).

10.5 Removing an Arbitrary Element

heapq has no remove(x) operation. You can:

• Search linearly for x, swap with last, pop, sift up/down — O(n) for the search.
• Use lazy deletion: maintain a “removed” set; when popping, skip removed entries. Amortized fine for many uses.

10.6 Heaps Aren’t Stable

If you need FIFO order among equal-priority items, use the tiebreaker counter trick.

10.7 Confusing Heap (Data Structure) With Heap (Memory Region)

Two completely unrelated meanings of “heap.” The data structure has nothing to do with the memory area where dynamically-allocated objects live.

11. Diagram — Sift Up vs Sift Down

flowchart LR
    subgraph SU [Sift Up after insert]
        S1[Insert at end] --> S2[Compare with parent]
        S2 --> S3{smaller?}
        S3 -- yes --> S4[Swap with parent]
        S4 --> S2
        S3 -- no --> S5[Done]
    end
    subgraph SD [Sift Down after extract]
        D1[Move last to root] --> D2[Compare with smaller child]
        D2 --> D3{larger than smaller child?}
        D3 -- yes --> D4[Swap with smaller child]
        D4 --> D2
        D3 -- no --> D5[Done]
    end

What this diagram shows. The two heap-maintenance operations are mirror images. Sift-up restores the heap property after a leaf insert (the new element might be too small for its position); sift-down restores it after the root is replaced by the previous-last element (the replacement might be too large for the root). Both are O(log n).

12. Heap Variants Worth Knowing

• Binary heap — what we’ve described. The standard.
• d-ary heap — each node has d children instead of 2. Shorter, fatter tree. Better cache behavior; theoretically faster for graph algorithms with frequent decrease-key. d = 4 is a sweet spot in practice.
• Binomial heap — supports O(log n) merge of two heaps (binary heaps need O(n)).
• Fibonacci heap — O(1) amortized decrease-key; theoretical foundation of the optimal Dijkstra. Constants are large; rarely faster than binary heap in practice.
• Pairing heap — simpler than Fibonacci, similar amortized bounds (some unproven), competitive in practice.
• Skew heap / leftist heap — self-adjusting variants; merge in O(log n) without strict balancing rules.
• Min-max heap — supports both min and max in O(1); min and max each at known positions.

13. Open Questions

• When does d-ary heap (d=4) beat binary heap in practice for Dijkstra? Empirically yes for sparse graphs, but the difference is small.
• Why is Fibonacci heap rarely faster despite theoretical superiority? Constants and pointer overhead dominate; binary heap’s tight array layout wins on real hardware.

14. See Also

• Heap Sort — sorting with a heap (also under sorting)
• Top K Elements — heap-of-size-k pattern
• Two Heaps Pattern — running median
• K-Way Merge — heap-driven merge
• Dijkstra’s Algorithm — heap-based graph algorithm
• Huffman Coding — heap-driven greedy
• Big-O Notation — for the build-heap O(n) analysis
• Amortized Analysis — for Fibonacci heap’s bounds
• SWE Interview Preparation MOC