Heaps and Priority Queues

The mental model: a screaming bureaucrat

Imagine a corporate org chart where the only rule is every manager earns less than their direct reports (replace "earns less" with "has smaller key" and you have a min-heap). The CEO at the top always earns the least. When the CEO leaves, the rule forces a reorganization — but only along one root-to-leaf path. When a new hire joins at the bottom, they might bubble up if they outrank their manager, but again only along one path. Neither operation touches the rest of the tree.

That path length is what makes heap operations O(log n). The tree is complete — every level is full except possibly the last, which fills left to right — so height is always exactly ⌊log₂ n⌋. Ten thousand employees, 13 levels of management. Ten million, 23 levels. The tree stays short no matter how many elements you add.

The array trick: no pointers needed

This is what makes heaps genuinely elegant. You don't allocate tree nodes with left/right pointers. You store the heap in a plain array and derive the tree structure from index arithmetic.

index:  0   1   2   3   4   5   6
value: 10  20  15  30  40  25  50

     10          (index 0)
    /  \
  20    15        (indices 1, 2)
 / \   / \
30  40 25  50     (indices 3, 4, 5, 6)

The mapping:

• Parent of node i: (i - 1) // 2
• Left child of node i: 2i + 1
• Right child of node i: 2i + 2

That's it. No malloc, no pointers, no node objects. The tree is an illusion the index arithmetic draws. This makes heaps extremely cache-friendly — the array is contiguous, so the CPU prefetcher loves it. Compare that to a binary search tree, which is a web of heap-allocated nodes scattered across memory.

flowchart TD
    A["index 0 → 10"]
    B["index 1 → 20"]
    C["index 2 → 15"]
    D["index 3 → 30"]
    E["index 4 → 40"]
    F["index 5 → 25"]
    G["index 6 → 50"]
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    style A fill:#7c5cff,color:#fff
    style C fill:#22d3ee,color:#0a0a0f

One concrete thing to internalize: the right subtree of the root (index 2) and its descendants are not necessarily larger than the left subtree. The heap only guarantees each parent ≤ its children. Siblings are unordered. That's weaker than BST ordering and it's exactly why you can't search for arbitrary elements — but it's enough to always find the minimum in O(1).

The two operations that define the heap

Every other operation is built on these two primitives.

Sift-up (used after insert)

Push the new element to the end of the array. Then walk it upward, swapping with its parent whenever it violates the heap property.

def push(heap, val):
    heap.append(val)
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] <= heap[i]:   # min-heap: parent already smaller, done
            break
        heap[parent], heap[i] = heap[i], heap[parent]
        i = parent

Worst case: the new element is the global minimum and bubbles all the way to the root. That is log n swaps.

Sift-down (used after extract-min)

Pop the root (your answer). Copy the last element to the root position and shrink the array. Then walk the new root downward, swapping with the smaller of its two children at each step until the property is restored.

def pop(heap):
    if len(heap) == 1:
        return heap.pop()
    min_val = heap[0]
    heap[0] = heap.pop()       # move last element to root
    i = 0
    n = len(heap)
    while True:
        left, right = 2 * i + 1, 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
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest
    return min_val

The key detail in sift-down: you always swap with the smaller child. If you swap with the larger child, you'd put a smaller element above a larger sibling, which could violate the property there.

{ "type": "heap", "variant": "min", "title": "insert 5 → sift-up; extract-min → sift-down", "data": [10, 20, 15, 30, 40, 25, 50] }

Hit the insert animation and watch 5 arrive at the end and swap up to the root. Then extract-min: 50 teleports to the root and sinks back down. That left-to-right level-by-level scan IS the array. The indices are the tree.

heapify: O(n) build, not O(n log n)

Given an unordered array, you can build a heap by calling push n times — O(n log n). But there's a better way.

Heapify starts from the last non-leaf node (index n//2 - 1) and calls sift-down on every node going right-to-left up to the root:

def heapify(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        _sift_down(arr, i, n)

Why O(n)? Intuitively: most nodes are leaves and do zero work. Half the nodes are leaves (no sift-down). A quarter do at most one swap. An eighth do at most two. Summing that geometric series gives 2n work total — O(n). The formal proof uses the sum Σ h·(n/2^h) which converges to 2n.

This matters in practice. If you're given 10 million items and need the smallest 100, building the heap with heapify is O(10M) then 100 pops at O(log 10M) ≈ 23 each. Using sort instead is O(10M · log 10M) ≈ O(240M). That's a real difference at scale.

In Python, heapq.heapify(arr) does this in-place on any list. Use it.

The patterns heaps unlock

Top-K elements

The single most common heap question. You've got a million numbers and want the 10 largest.

Wrong approach: sort descending, take the first 10. O(n log n). Fine for small n, wrong instinct to build.

Heap approach: maintain a min-heap of size K. Stream through all n elements. For each new element, if it's larger than the heap's min (the root), pop the min and push the new element. At the end, the heap contains exactly the K largest.

import heapq

def top_k_largest(nums, k):
    # maintain a min-heap of size k
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)      # evict the smallest of our k candidates
    return sorted(heap, reverse=True)

Time: O(n log k). Space: O(k). When k is small (top-10 in a billion-row table), this is vastly better than sorting. See top-K elements for the full technique treatment and its variants.

Merge K sorted lists

You have K sorted arrays and want one sorted output. The naive approach concatenates and sorts — O(N log N) where N is total elements. The heap approach is O(N log K):

import heapq

def merge_k_sorted(lists):
    result = []
    heap = []
    # seed: first element from each list, along with which list it came from
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))  # (value, list_idx, elem_idx)

    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        next_idx = elem_idx + 1
        if next_idx < len(lists[list_idx]):
            heapq.heappush(heap, (lists[list_idx][next_idx], list_idx, next_idx))

    return result

The heap size never exceeds K. Each of the N total elements gets pushed and popped once — O(log K) per operation, O(N log K) total. This exact pattern shows up in external sort, distributed database query execution, and anywhere you're merging presorted shards.

Running median

Keep the median of a stream of integers as they arrive. Two heaps: a max-heap for the lower half, a min-heap for the upper half. Balance their sizes so they differ by at most 1. The median is either the max-heap's root (if lower half is larger) or the average of both roots (if equal size).

import heapq

class MedianFinder:
    def __init__(self):
        self.lower = []   # max-heap (negate values)
        self.upper = []   # min-heap

    def add_num(self, num):
        # push to lower, then rebalance
        heapq.heappush(self.lower, -num)
        # make sure all of lower ≤ all of upper
        if self.upper and -self.lower[0] > self.upper[0]:
            heapq.heappush(self.upper, -heapq.heappop(self.lower))
        # balance sizes: lower may have at most one extra
        if len(self.lower) > len(self.upper) + 1:
            heapq.heappush(self.upper, -heapq.heappop(self.lower))
        elif len(self.upper) > len(self.lower):
            heapq.heappush(self.lower, -heapq.heappop(self.upper))

    def find_median(self):
        if len(self.lower) > len(self.upper):
            return -self.lower[0]
        return (-self.lower[0] + self.upper[0]) / 2

Each add is O(log n). Each find is O(1). If someone asks you "how would you compute the running median over a sensor stream?" this is the answer, and it's not obvious the first time you see it.

Using heaps in practice

Python ships heapq, a min-heap operating in-place on a regular list. There is no max-heap — negate your values.

import heapq

data = [5, 1, 8, 2, 9]
heapq.heapify(data)          # O(n), in-place
heapq.heappush(data, 3)      # O(log n)
smallest = heapq.heappop(data)  # O(log n)
peek = data[0]               # O(1), no pop needed

# max-heap trick: negate
max_heap = [-x for x in data]
heapq.heapify(max_heap)
largest = -heapq.heappop(max_heap)

Java has PriorityQueue, min by default:

PriorityQueue<Integer> minH = new PriorityQueue<>();
PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());

Go requires implementing heap.Interface — heap is in container/heap. Worth doing once; after that, copy-paste your template.

One practical gotcha in all languages: you can't efficiently update an element's priority after it's been pushed. If you push a task with priority 5 and later want to change it to 2, the heap has no idea where that element lives. Standard workaround: "lazy deletion" — mark the old entry as stale (via a set of invalidated entries) and skip it when you pop it. Dijkstra's shortest-path often uses this pattern.

Pitfalls and anti-patterns

Using a heap when you need sorted order. A heap is not a sorted array. You can pop elements out in sorted order (heap sort), but the internal array is not sorted — heap[1] is not the second smallest. If you need random access by rank, sort the array and binary search, or reach for an order-statistics tree.

Building with n pushes instead of heapify. If you have all the elements upfront, heapq.heapify is O(n). Pushing one-by-one is O(n log n). This is a 10–20x difference at a million elements. Profile this once and you'll never forget.

Confusing min-heap and max-heap semantics. In an interview, be explicit. Say "min-heap" or "max-heap." Python's heapq is always min; the negation trick works but is easy to mess up under pressure — add a comment.

Not realizing the heap only guarantees the root. It's tempting to assume heap[k] is the k-th smallest. It isn't. The heap only guarantees parent ≤ children; siblings can be in any order. This bites people who try to use data[1] to get the second smallest without popping.

Using a heap when the queue is the right tool. If your "priorities" are just insertion order (FIFO), you want a plain queue — O(1) enqueue and dequeue. Heaps add log-n overhead to handle general priorities. Use the simpler tool when priorities are uniform.

When NOT to use a heap

You need this	Use this instead
Sorted order with random access by rank	Sorted array + binary search
O(log n) search/insert/delete by value	Binary search tree
FIFO ordering, priorities are all equal	Queue
Min AND max in O(1) simultaneously	Min-max heap or two separate heaps
Decrease-key efficiently (Dijkstra's classic form)	Fibonacci heap (theory), lazy deletion (practice)

The heap is excellent at exactly one thing: getting you the current extreme element cheaply under a mix of inserts and extracts. When your problem has that shape — running leaderboard, task scheduler, K-way merge, stream statistics — it fits perfectly. When it doesn't, don't force it.

If you're still orienting, a binary search tree gives you more structural ordering (find the 5th element, range queries), and a plain queue handles FIFO without the log-n overhead. Know both; reach for the heap when you catch yourself thinking "I always need the current smallest."