Heaps & Priority Queues

A heap is a tree that gives up on being fully ordered in exchange for being cheap to keep balanced. Where a BST insists that everything left of a node is smaller and everything right is larger, a heap only insists that a parent is smaller (or larger) than its own children — nothing about siblings, nothing about left versus right. That relaxation is the whole point: it's just barely enough structure to answer "what's the smallest (or largest) thing in here?" in O(1) and to keep the tree naturally balanced with almost no bookkeeping, which is exactly what you want for a priority queue — a job scheduler always running the next-highest-priority task, Dijkstra's algorithm always expanding the nearest unvisited node, a hospital triage system always calling the most critical patient next. Interviewers reach for heaps constantly because "give me the smallest/largest/k-th element, repeatedly, with the set changing" is one of the most common shapes an interview problem takes, and a heap is almost always the efficient answer.

This page assumes you've read trees-and-bst.html — heaps are a different, weaker invariant on the same binary-tree shape, and the contrast with a BST is the fastest way to understand why a heap looks the way it does.

Deep Dive: The Heap Property — Weaker Than a BST, and Why That's the Point

A BST's invariant is global and directional — it tells you exactly which of two arbitrary nodes anywhere in the tree is bigger, which is what lets you binary-search it. A heap's invariant is local and one-directional — it only compares a node to its own immediate children, never to a sibling, a cousin, or anything not on a direct ancestor-descendant line. That's strictly less information, and that's exactly why it's cheaper: restoring the heap property after a change only ever requires walking a single root-to-leaf path (height h, so O(log n) for a balanced binary tree) comparing and swapping with a parent or a child, never rebalancing a whole subtree or performing rotations. You also never need to decide which child goes left versus right, so insertion can just fill the next open slot left-to-right, top-to-bottom — which is precisely what keeps a heap always shaped as a complete binary tree (every level full except possibly the last, filled left to right) with no extra balancing logic required at all.

Deep Dive: Array Representation — No Pointers Needed

Because a heap is always a complete binary tree (no gaps except possibly a partially-filled last level), you can store the entire structure in a plain array and derive every parent/child relationship from index arithmetic alone — no left/right/parent pointers, no per-node object overhead. This is a direct payoff of the heap property being weaker than a BST's: a BST can be any shape at all (skewed, sparse, unbalanced) so it needs real pointers to represent arbitrary structure, but a heap's shape is always exactly "fill left to right, level by level" and nothing else, so the shape itself is predictable enough to encode as a formula. The practical win is real: no pointer-chasing means better cache locality, no per-node memory overhead for pointers, and O(1) index math instead of a chain of dereferences to find a parent or child.

Deep Dive: Heapify-Up — Restoring the Property After Insert

def push(self, val):
    self.a.append(val)
    i = len(self.a) - 1
    while i > 0 and self.a[i] < self.a[self.parent(i)]:
        par = self.parent(i)
        self.a[i], self.a[par] = self.a[par], self.a[i]
        i = par

A new element always gets appended at the next open array slot (the next leaf position in the complete tree), which trivially preserves the shape but might break the ordering property — the new leaf could be smaller than its parent in a min-heap. Heapify-up fixes exactly that: compare the new element to its parent, and if it violates the property, swap them and repeat the check one level up. Because a heap only cares about parent-vs-child (not siblings), fixing the ONE broken relationship — the new node and its parent — by swapping never breaks any relationship elsewhere; the new node's old parent is now the new node's sibling relationship, which the heap property never constrains. The walk terminates the moment the element reaches a parent it's not smaller than, and since it climbs one level at a time up a tree of height O(log n), the whole operation is O(log n).

Deep Dive: Heapify-Down — Restoring the Property After Removing the Root

def pop(self):
    root = self.a[0]
    last = self.a.pop()
    if self.a:
        self.a[0] = last
        self._sift_down(0)
    return root

def _sift_down(self, i):
    n = len(self.a)
    while True:
        l, r, smallest = 2*i + 1, 2*i + 2, i
        if l < n and self.a[l] < self.a[smallest]: smallest = l
        if r < n and self.a[r] < self.a[smallest]: smallest = r
        if smallest == i: break
        self.a[i], self.a[smallest] = self.a[smallest], self.a[i]
        i = smallest

You can't just delete the root and leave a hole — the array (and the complete-tree shape it encodes) would have a gap. The standard trick is to move the very last element into the vacated root slot, which keeps the tree complete (you removed exactly one leaf-position's worth of elements), but almost certainly breaks the heap property at the top, since the last element was wherever it happened to land, not necessarily small. Heapify-down repairs that by repeatedly comparing the misplaced element to its smaller child (min-heap) and swapping downward until it's no longer bigger than either child or it runs out of children. Same logic as heapify-up, mirrored: one broken relationship, fixed by walking a single root-to-leaf path, so again O(log n).

Deep Dive: Building a Heap From an Unsorted Array in O(n)

Sifting down from the bottom instead of inserting one at a time gets you the same valid heap for less total work, and the reason is a fact that surprises most people the first time they see it: most nodes in a tree are near the bottom. In a complete binary tree, roughly half the nodes are leaves (height 0, nothing to sift), roughly a quarter are one level up (height 1, at most 1 swap), and so on — the number of nodes at height h shrinks by half every level while the work per node (its height, the max distance it could possibly sift) only grows by 1. Summing "count of nodes at height h" times "at most h swaps" across all levels of a complete tree converges to a small constant times n rather than n log n — that's the O(n) result. You don't need to reproduce the summation to use this in an interview; you do need to know it's O(n), that it works by sifting DOWN from the last internal node backwards to the root (not sifting up from the front), and that inserting one-at-a-time is the O(n log n) alternative it beats.

Deep Dive: Heap Sort

Heap sort is the heap's own O(n) build step plus n applications of "remove the max", done cleverly in place: instead of allocating a separate output array, each removed max is dropped into the slot the shrinking heap just vacated at the end of the array, so the array ends up sorted with zero extra memory beyond the heap itself. Build is O(n) as shown above, and then there are n-1 removals, each an O(log n) sift-down over a shrinking region, giving O(n log n) total — matching merge sort and the best case of quicksort, but with O(1) auxiliary space (merge sort needs O(n), quicksort's recursion stack needs O(log n)). The trade-off is that heap sort is not stable (it can reorder equal elements relative to each other, because sifting swaps across the tree structure, not adjacent equal-comparing elements) and it has worse real-world cache behavior than quicksort because heap operations jump around the array by index arithmetic (parent/child) rather than scanning it sequentially.

Key Pointers

• The heap property is local (parent vs. its own children only) and one-directional, unlike a BST's global left-<-node-<-right ordering — that weaker guarantee is exactly what makes heap operations cheap.
• A heap is always a complete binary tree (filled left to right, level by level), which lets it live in a plain array: children of index i are at 2i+1 and 2i+2, parent is at (i-1)//2.
• Insert = append then heapify-up (bubble toward the root while smaller than parent, min-heap); both are O(log n) because they walk one root-to-leaf path.
• Remove-root = move the last element to the root, shrink, then heapify-down (sift toward the smaller/larger child until in place); also O(log n) for the same reason.
• Building a heap from an unsorted array by sifting down from the last internal node backwards is O(n), not O(n log n) — most nodes are near the bottom and have little height to sift through.
• Heap sort = build a max-heap, then repeatedly swap the root to the end of the active region and shrink — O(n log n) time, O(1) extra space, not stable.
• A priority queue is an abstract data type ("give me the highest-priority item next"); a heap is just the efficient array-backed way to implement one in O(log n) per operation.
• Heaps only give you fast access to the min (or max) — they do not support fast arbitrary search or in-order traversal the way a BST does. Don't reach for a heap when you need "find element X" or "give me everything sorted between A and B".

How It Works

1. To insert a value: append it to the end of the array (the next available leaf slot), then heapify-up — repeatedly compare it to its parent and swap while it violates the heap property, stopping when it doesn't or it reaches the root.
2. To peek the min/max: it's always array[0] by the heap property — O(1), no traversal needed.
3. To remove the min/max: save array[0], move the last element into index 0, shrink the array by one, then heapify-down — repeatedly compare the new root to its smaller (min-heap) or larger (max-heap) child and swap while it violates the property, stopping when it doesn't or it reaches a leaf.
4. To build a heap from an unsorted array: iterate the internal (non-leaf) node indices backwards, from n//2 - 1 down to 0, calling heapify-down at each — this is Floyd's algorithm and runs in O(n) total.
5. To sort with a heap: build a max-heap over the whole array (O(n)), then repeat n-1 times: swap the root with the last element of the still-unsorted region, shrink that region by one, and heapify-down the new root within it.
6. To decide min-heap vs. max-heap for a problem: min-heap when you repeatedly need the smallest remaining item (Dijkstra's next-closest node, merging k sorted lists); max-heap when you need the largest (top-k largest streaming values, a scheduler running highest-priority-first).
7. To reason about whether a heap fits a problem at all: ask if you only ever need "smallest/largest so far" repeatedly, with insertions and removals interleaved — if you also need arbitrary lookup, ordered iteration, or range queries, a heap alone is the wrong structure.

Try It Yourself

A full array-backed min-heap (push/pop), a heapify-up insertion trace, the O(n) build-heap step compared against one-at-a-time inserts by swap count, and heap sort.

class MinHeap:
    def __init__(self):
        self.a = []

    def parent(self, i): return (i - 1) // 2
    def left(self, i): return 2 * i + 1
    def right(self, i): return 2 * i + 2

    def push(self, val):
        self.a.append(val)
        i = len(self.a) - 1
        while i > 0 and self.a[i] < self.a[self.parent(i)]:
            self.a[i], self.a[self.parent(i)] = self.a[self.parent(i)], self.a[i]
            i = self.parent(i)

    def pop(self):
        root = self.a[0]
        last = self.a.pop()
        if self.a:
            self.a[0] = last
            self._sift_down(0)
        return root

    def _sift_down(self, i):
        n = len(self.a)
        while True:
            l, r, smallest = self.left(i), self.right(i), i
            if l < n and self.a[l] < self.a[smallest]: smallest = l
            if r < n and self.a[r] < self.a[smallest]: smallest = r
            if smallest == i: break
            self.a[i], self.a[smallest] = self.a[smallest], self.a[i]
            i = smallest

def build_heap_on(values):
    """Floyd's build-heap: sift-down from the last internal node backwards. O(n)."""
    a = list(values); n = len(a); swaps = 0
    def sift_down(i):
        nonlocal swaps
        while True:
            l, r, smallest = 2*i+1, 2*i+2, i
            if l < n and a[l] < a[smallest]: smallest = l
            if r < n and a[r] < a[smallest]: smallest = r
            if smallest == i: break
            a[i], a[smallest] = a[smallest], a[i]
            swaps += 1
            i = smallest
    for i in range(n // 2 - 1, -1, -1):
        sift_down(i)
    return a, swaps

def heap_sort(values):
    a = list(values); n = len(a)
    def sift_down_max(i, size):
        while True:
            l, r, largest = 2*i+1, 2*i+2, i
            if l < size and a[l] > a[largest]: largest = l
            if r < size and a[r] > a[largest]: largest = r
            if largest == i: break
            a[i], a[largest] = a[largest], a[i]
            i = largest
    for i in range(n // 2 - 1, -1, -1):
        sift_down_max(i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down_max(0, end)
    return a

# heapify-up insert trace
values = [5, 2, 8, 1, 9, 3]
h = MinHeap()
for v in values:
    h.push(v)
print("final heap array          :", h.a)
popped = [h.pop() for _ in range(len(h.a))]
print("pop order (should be sorted):", popped)

arr = [9, 4, 7, 1, 2, 6, 3, 8, 5]
built, build_swaps = build_heap_on(arr)
print("build_heap(O(n)) result    :", built)
print("build_heap(O(n)) swaps used:", build_swaps)

data = [5, 2, 8, 1, 9, 3, 7]
print("heap_sort output :", heap_sort(data))

# Output:
# final heap array          : [1, 2, 3, 5, 9, 8]
# pop order (should be sorted): [1, 2, 3, 5, 8, 9]
# build_heap(O(n)) result    : [1, 2, 3, 4, 9, 6, 7, 8, 5]
# build_heap(O(n)) swaps used: 4
# heap_sort output : [1, 2, 3, 5, 7, 8, 9]

Common Mistakes & Interview Traps

• Assuming a heap is sorted, or that array[1] is the second-smallest element — a heap only guarantees parent <= children; the second-smallest could be at index 1 or 2, and nothing about sibling order is guaranteed.
• Assuming array[0] to array[n-1] traversal (or an inorder-style walk) gives sorted output the way it does on a BST — it does not; that's a different invariant entirely.
• Forgetting that building a heap from an unsorted array should sift DOWN from the last internal node backwards (O(n)), not insert one at a time with heapify-up (O(n log n)) — both produce a valid heap, but only one is optimal, and interviewers ask this specifically to test if you know why.
• Using a max-heap when you need the k smallest elements, or vice versa — for "top k largest streaming values" you actually want a MIN-heap of size k (so you can cheaply evict the smallest of your current top-k when a bigger one arrives), which trips people up because the intuition initially points the wrong way.
• Treating a heap as a substitute for a BST when the problem needs "find an arbitrary element" or "give me a sorted range" — a heap only gives fast access to the current min/max, not arbitrary search, which is O(n) in a heap.
• Forgetting heap sort is not stable, and using it in a context where equal-key elements' relative order matters (e.g. sorting already-sorted-by-first-name records by last name) without checking.

Interview Q&A

Q: What's the heap property, and how is it weaker than a full BST ordering?

A: A min-heap requires every parent to be less than or equal to both of its children; a max-heap requires the reverse. That's a purely local, one-directional constraint between a node and its own children — it says nothing about how siblings, cousins, or any two nodes not on a direct ancestor line compare. A BST's invariant is global: every node splits the entire tree into "everything smaller" and "everything larger," which is strictly more information and is what makes a BST searchable in a way a heap isn't.

Q: Why does that weaker property let heap operations be simpler/faster than a general BST?

A: Because the only invariant that can ever be broken is a single parent-child relationship, fixing it never requires touching more than one root-to-leaf path (bubbling up or sifting down), and there's no need to decide "which side" a new element goes on the way a BST does — it just fills the next open slot. That also means a heap never needs rotations or rebalancing logic: its complete-tree shape is automatically maintained by "always insert at the next open slot, always remove from the end," which a BST's arbitrary shape can't rely on.

Q: How is a binary heap stored in a plain array, and how do you find a node's children from its index?

A: The heap is stored level by level, left to right, with no gaps (it's always a complete binary tree), so for a node at index i: left child is at 2i+1, right child is at 2i+2, and parent is at (i-1)//2 using integer division. This works only because the shape is guaranteed complete — an arbitrary binary tree couldn't be encoded this compactly, which is why a BST needs real pointers instead.

Q: Walk through heapify-up after inserting a new element.

A: The new element is appended at the array's next open slot (the next leaf position). Compare it to its parent at index (i-1)//2; if it violates the heap property (smaller than its parent, in a min-heap), swap them, update i to the parent's index, and repeat. Stop when the element is no longer smaller than its parent or it reaches the root (index 0). Because this climbs one level per comparison up a tree of height O(log n), the whole operation is O(log n).

Q: Why is building a heap from an unsorted array O(n) and not O(n log n)?

A: Because most nodes in a complete binary tree are near the bottom — half are leaves that need zero work, a quarter are one level up with at most 1 possible swap, and so on — while sifting down from the last internal node backwards only does as much work at each node as its height, not the full tree height. Summing "nodes at height h" times "at most h swaps" across all levels converges to O(n) rather than O(n log n), unlike inserting one element at a time (which is always O(log n) per insert regardless of position, giving O(n log n) total).

Q: How does heap sort use a heap to sort in place?

A: Build a max-heap over the whole array in O(n). Then repeat n-1 times: swap the root (the current maximum) with the last element of the still-active region, shrink the active region by one so that swapped-out max is now permanently in its final sorted position, and sift-down the new root within the smaller region to restore the heap property. After all swaps, the array is sorted ascending, using zero extra memory beyond the original array.

Q: Name two real systems/algorithms that rely on a priority queue.

A: Dijkstra's shortest-path algorithm uses a min-heap to always expand the currently-nearest unvisited node next, which is what keeps it from re-scanning the whole frontier at every step. OS and job schedulers use a priority queue to always run the highest-priority (or earliest-deadline) ready task next rather than scanning every pending job to find it.

Follow-up: You need the k largest elements out of a huge stream you can only pass over once. Why a min-heap of size k and not a max-heap?

A: Keep a min-heap capped at size k: push each new value, and if the heap exceeds size k, pop the min. The heap's root is always the smallest of your current "top k," so it's exactly the value you want to evict when something bigger shows up — checking and evicting is O(log k). A max-heap would put the largest value at the root, which is the one thing you never want to remove, so you'd have no cheap way to find and evict the current k-th largest when a bigger value arrives.

Follow-up: Someone claims "a heap is just a faster sorted array." What's wrong with that framing?

A: A heap is not sorted — it only guarantees parent-vs-children ordering, not a full linear order, so you cannot binary search it or read it off in sorted order without popping every element (which is exactly heap sort, an O(n log n) operation, not a free read). A sorted array gives O(log n) search and O(1) access to any rank, which a heap does not provide at all — a heap trades away general ordering for O(log n) insert/remove-min, which a sorted array doesn't give you (insert into a sorted array is O(n)).

Follow-up: What happens to heap operations if you implement a heap with actual node objects and pointers instead of an array?

A: It still works correctly — the heap property doesn't require an array — but you lose the O(1) index-math parent/child lookup and need to either store parent pointers explicitly or track the current size to compute the next insertion point (the next open complete-tree slot is harder to find without the array's implicit indexing). You also lose cache locality since heap operations become pointer-chasing instead of index arithmetic over contiguous memory, which is real overhead for no benefit here since a heap's shape is always predictable enough for the array encoding to work.

Trade-offs

A heap is the right structure whenever you need repeated access to the current min or max while the set keeps changing — a priority queue, a scheduler, Dijkstra's frontier, streaming top-k — because it gives O(log n) insert and remove-min/max with O(1) peek and low constant-factor overhead thanks to the array representation. It is the wrong choice the moment you need more than that: arbitrary search for a specific value is O(n) in a heap (no ordering to exploit, unlike a BST's O(log n) when balanced), it can't give you a sorted range or "the next value after X" without popping everything in between, and it doesn't support efficient arbitrary-key decrease/increase without either a linear scan or an auxiliary index tracking each value's array position (as real Dijkstra implementations typically do, since "decrease-key" isn't a native heap operation). If you need ordered iteration or range queries, reach for a balanced BST or a sorted structure instead; if you only ever need "insert and eventually pop everything in sorted order" without interleaving, a plain sort is simpler and has the same asymptotic cost as heap sort with fewer moving parts.

PracticeSolve related problems in the 150 →