Skip to content
Hari KharelStudy

Heaps and priority queues

coreCommon atGoogleAmazonMetaAnthropicStripeRead firstArraysBinary treesPractise in the Sandbox →

A binary heap is a complete binary tree packed into an array, where every parent is ≤ its children (a min-heap). That one rule puts the minimum at index 0, so peek is O(1). Push and pop break the rule along a single root-to-leaf path and fix it by swapping, so both are O(log n). A priority queue is the interface; a heap is the usual implementation.

The idea in plain words

Section titled “The idea in plain words”

Think of a company org chart where every manager is more senior than everyone who reports to them. The CEO, at the top, is the most senior person in the company. Nobody had to sort the whole company to know that; the rule “boss beats direct reports” is enough.

That’s the heap property. It is much weaker than sorted order:

  • Siblings have no order between them. The left child can be bigger or smaller than the right.
  • You only know the top for sure. The second smallest is one of the root’s two children, but which one is unknown until you look.

Being weaker is the point. Keeping a list fully sorted costs O(n) per insert. Keeping “parent beats children” costs O(log n), because a broken rule can only be broken along one path, and a complete tree with n nodes is only ⌊log₂ n⌋ levels tall.

Why an array? A complete tree (every level full except the last, which fills left to right) has no gaps. So node i can find its family by arithmetic: parent at (i−1)//2, children at 2i+1 and 2i+2. No pointers, no node objects, great cache behaviour.

See it

Section titled “See it”

Push values and pop the root. Watch the same swap happen in the tree and in the array at once: the tree is just a way of drawing the array. Switch to a max-heap to flip the rule, or type a list and heapify it in place.

Heap sandbox: tree and array are the same thing
push · pop · heapify
operate
 
as a tree
7[3]9[4]3[1]8[5]5[6]2[2]1[0]
as the backing array
1
3
2
7
9
8
5
0123456
parent(i) = (i−1)//2 · left(i) = 2i+1 · right(i) = 2i+2
size7
min1
height2
value being movedcomparedsettledremoved
A min-heap built from 5, 9, 2, 7, 3, 8, 1. Push or pop to watch it repair itself.
1 / 1
Operation log
Push a value or pop the root. Each line shows how many swaps the repair took.

Things to try:

  • Push 0 into the min-heap. It climbs all the way to the root: the worst case, one swap per level.
  • Push a large value. It stays where it landed: zero swaps.
  • Pop several times in a row. The values come out sorted. That’s heap sort.

When to reach for it

Section titled “When to reach for it”
The problem says… Why a heap fits
“the k largest / smallest / closest …” A size-k heap keeps only the candidates: O(n log k), not O(n log n).
“repeatedly take the cheapest / earliest / highest-priority item, then add new ones” Interleaved inserts and extract-min are exactly what a heap is for.
“process events in time order as they’re scheduled” A min-heap keyed on time is an event queue. See event-driven simulation.
shortest path with weights, Prim’s MST The frontier is a priority queue keyed on distance. See shortest paths.
“merge many sorted sources” A heap of the heads of each source picks the next smallest in O(log k).

How it works

Section titled “How it works”
  1. Push: append the new value at the end of the array. The tree is still complete.
  2. Sift up: while the value is smaller than its parent at (i−1)//2, swap them. At most one swap per level.
  3. Pop: the answer is a[0].
  4. Move the last element into the root’s slot and shrink the array. Again the shape stays complete.
  5. Sift down: while the value is bigger than its smaller child, swap with that child. Picking the smaller child is what keeps the other subtree valid.

You’ll rarely write this in Python or C#, but you must in TypeScript, and interviewers sometimes ask for it anyway. Here are the guts:

min_heap.py
import heapq




class MinHeap:
    """Binary min-heap on a plain list. heapq does exactly this; here are the guts."""


    def __init__(self) -> None:
        self.a: list[int] = []


    def push(self, x: int) -> None:
        a = self.a
        a.append(x)                      # 1. put it in the first free slot
        i = len(a) - 1
        while i > 0:                     # 2. sift up while smaller than the parent
            p = (i - 1) // 2
            if a[p] <= a[i]:
                break
            a[i], a[p] = a[p], a[i]
            i = p


    def pop(self) -> int:
        a = self.a
        top = a[0]                       # 3. the root is the minimum (IndexError if empty)
        last = a.pop()
        if a:
            a[0] = last                  # 4. move the last element into the hole
            i, n = 0, len(a)
            while (c := 2 * i + 1) < n:  # 5. sift down toward the smaller child
                if c + 1 < n and a[c + 1] < a[c]:
                    c += 1
                if a[i] <= a[c]:
                    break
                a[i], a[c] = a[c], a[i]
                i = c
        return top




if __name__ == "__main__":
    h, ref = MinHeap(), []
    for x in [5, 9, 2, 7, 3, 8, 1]:
        h.push(x)
        heapq.heappush(ref, x)
    assert h.a == ref                     # same layout as the stdlib
    assert [h.pop() for _ in range(7)] == [1, 2, 3, 5, 7, 8, 9]
    print("ok")

Top k with a size-k heap

Section titled “Top k with a size-k heap”

To find the k largest, keep a min-heap of size k. That sounds backwards until you see the root’s job: it is the weakest member of the current top k, the bar a newcomer has to clear. Anything that can’t beat it is dropped in one comparison. Anything that can, replaces it in O(log k).

Top k with a size-k min-heap
step through
incoming stream
4
1
7
3
8
5
9
2
6
10
3
7
01234567891011
min-heap, size ≤ 3
(empty tree)
backing array
·
k3
bar (root)–
comparisons0
sort would be ≈43
entered the heapevicted / rejectedthe barfinal top k
Goal: the 3 largest values. Keep a min-heap of at most 3. Its root is the smallest of the best-so-far: the bar a newcomer must beat.
1 / 19
top_k.py
import heapq




def k_largest(xs: list[int], k: int) -> list[int]:
    """The k largest values, largest first, in O(n log k) time and O(k) space."""
    if k <= 0:
        return []
    heap: list[int] = []                 # min-heap: heap[0] is the weakest of the best k
    for x in xs:
        if len(heap) < k:
            heapq.heappush(heap, x)      # 1. fill up to k
        elif x > heap[0]:
            heapq.heapreplace(heap, x)   # 2. beat the bar: pop root + push x in one sift
        # 3. otherwise x can't be in the top k: drop it in O(1)
    return sorted(heap, reverse=True)    # 4. k log k to report in order




if __name__ == "__main__":
    data = [4, 1, 7, 3, 8, 5, 9, 2, 6, 10, 3, 7]
    assert k_largest(data, 3) == [10, 9, 8]
    assert k_largest(data, 3) == heapq.nlargest(3, data)  # the stdlib one-liner
    assert k_largest([2, 2, 1], 2) == [2, 2]             # duplicates count
    assert k_largest([1], 5) == [1]
    assert k_largest([], 2) == []
    print("ok")

The standard library, per language

Section titled “The standard library, per language”
Python heapq C# PriorityQueue<TElement, TPriority> TypeScript
Kind min-heap of functions over a plain list min-heap by priority (.NET 6+) none built in: hand-roll it (above)
Push / pop / peek heappush(h, x), heappop(h), h[0] Enqueue(e, p), Dequeue(), Peek(), TryDequeue(out e, out p) your class
Build from n items heapify(list) in O(n), in place EnqueueRange(...), or the constructor taking items bottom-up sift-down loop
Pop + push in one sift heapreplace (pop first), heappushpop (push first) DequeueEnqueue, EnqueueDequeue pop then push
Max-heap push -x, or (-priority, …) tuples; 3.14+ adds heappush_max, heappop_max, heapify_max pass Comparer<int>.Create((a, b) => b.CompareTo(a)) flip the comparator
One-liners nlargest(k, xs), nsmallest(k, xs), merge(*sorted_iters) none none
Remove arbitrary item not supported (O(n) by hand) Remove(...) (.NET 9+, O(n)) O(n) by hand

Under the hood, .NET’s PriorityQueue is a 4-ary heap (each node has four children): a shallower tree, so fewer levels to sift through.

Priorities and ties

Section titled “Priorities and ties”

Real priority queues hold things with priorities, and ties need a rule. Neither stdlib heap is stable (equal priorities can come out in any order), so add an increasing sequence number as the tie-breaker. In Python it also stops heapq from comparing the payloads, which raises TypeError for objects that don’t support <.

ties.py
import heapq
from itertools import count




def drain(jobs: list[tuple[str, int]]) -> list[str]:
    """Highest priority first; equal priorities come out in arrival (FIFO) order."""
    heap: list[tuple[int, int, str]] = []
    seq = count()                                # 1. a tie-breaker that only goes up
    for name, priority in jobs:
        # 2. negate for max-first (heapq is a min-heap); seq breaks ties and means
        #    Python never has to compare the payloads themselves
        heapq.heappush(heap, (-priority, next(seq), name))
    return [heapq.heappop(heap)[2] for _ in range(len(heap))]




if __name__ == "__main__":
    jobs = [("a", 1), ("b", 5), ("c", 5), ("d", 3), ("e", 5)]
    assert drain(jobs) == ["b", "c", "e", "d", "a"]


    # Python 3.14+ also has max-heap functions, no negation needed:
    if hasattr(heapq, "heappush_max"):
        h: list[int] = []
        for x in [3, 9, 4]:
            heapq.heappush_max(h, x)
        assert heapq.heappop_max(h) == 9
    print("ok")

What it costs

Section titled “What it costs”
Operation Binary heap Sorted array Unsorted array
peek min O(1) O(1) O(n)
push O(log n) O(n) (shift) O(1)
pop min O(log n) O(1) from the end O(n)
build from n items O(n) (heapify) O(n log n) O(1)
search / delete arbitrary O(n) O(log n) / O(n) O(n)
top k of n O(n log k) with a size-k heap O(n log n) O(n) average (quickselect)

Why O(log n): sift-up and sift-down move along one path, and a complete tree of n nodes has height ⌊log₂ n⌋. A million items is 19 levels.

Why heapify is O(n), not O(n log n): it sifts down from the bottom up. Half the nodes are leaves and don’t move. A quarter can sink one level, an eighth two levels, and so on. The total is n·(1/4 + 2/8 + 3/16 + …) ≤ n. Pushing items one at a time instead is O(n log n), because each newcomer may climb the full height.

How fast does work grow?
drag n
4080120160input size n →
n = 16
O(log n): 4 opsO(n): 16 opsO(n log n): 64 ops

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Max-heap. Same code, flipped comparison. In Python, negate the key.
  • Two heaps. A max-heap of the lower half and a min-heap of the upper half keeps a running “middle” at both tops. A classic pattern; rebalance so their sizes differ by at most one.
  • Lazy deletion. Heaps can’t delete from the middle cheaply, so mark items as dead (in a set or by a version number) and skip them when they reach the top. This is also how Dijkstra handles “decrease-key” with a stdlib heap: push the new, better entry and ignore the stale one later.
  • Indexed heap. Keep a position[item] map updated on every swap so you can change an item’s priority in O(log n). More code; rarely needed in interviews.
  • d-ary heap. Each node has d children. Pushes get cheaper (shorter tree), pops do more comparisons per level.
  • Heap sort. Heapify, then pop n times into the back of the same array. O(n log n), O(1) extra space, not stable.

Pitfalls

Section titled “Pitfalls”
  • Assuming the array is sorted. Only a[0] is guaranteed. heap[1] is not the second smallest. Printing the heap and seeing “almost sorted” values fools people.
  • Wrong heap direction for top k. k largest wants a min-heap of size k, and vice versa.
  • Comparing payloads on ties (Python TypeError, or non-determinism in C#). Use (priority, seq, item).
  • Mutating an item’s priority in place. The heap doesn’t notice; its invariant silently breaks. Push a new entry instead.
  • Popping from an empty heap. heappop([]) raises IndexError; Dequeue() throws InvalidOperationException. Check size or use TryDequeue.
  • Off-by-one in hand-rolled index math. 0-based: parent (i−1)//2, children 2i+1, 2i+2. 1-based: parent i//2, children 2i, 2i+1. Pick one and stick to it.

In the interview

Section titled “In the interview”
  • Say what goes in the heap and what the key is: “A min-heap of (distance, node). The root is always the closest unsettled node.”
  • For top k, say the bar argument out loud: “The root is the k-th best so far; anything below it can’t make the cut.” Then give O(n log k) time and O(k) space.
  • Mention heapify is O(n) if you build from a known batch.
  • Expect follow-ups: “What if k is close to n?” (sort, or flip to a heap of the n−k you’re discarding), “What if items’ priorities change?” (lazy deletion or an indexed heap), “What if the data doesn’t fit in memory?” (a size-k heap is O(k) memory and works on a stream).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
You want the 100 largest values from a stream of 10 million. Which structure, and roughly how much work?
Check yourself
pick one
A min-heap's array is [1, 4, 2, 9, 5, 3]. What is the second-smallest value, and where can it be in general?
Check yourself
pick one
Why is building a heap with heapify O(n), while pushing the same n items one by one is O(n log n)?

Practice on your own

Section titled “Practice on your own”

These are classic textbook exercises, not gym questions:

  • The k points closest to the origin from a list of (x, y) pairs.
  • Sort a k-sorted array (every element is at most k places from its sorted position) in O(n log k).
  • Minimum total cost to join ropes, where joining two ropes costs the sum of their lengths.
  • In-place heap sort, then explain why it isn’t stable.
  • “Last stone weight”: repeatedly smash the two heaviest stones and push back the difference.

Go deeper

Section titled “Go deeper”
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), ch. 6 “Heapsort”: heap property, BUILD-MAX-HEAP and the O(n) proof.
  • Sedgewick and Wayne, Algorithms §2.4, Priority Queues: swim/sink, indexed priority queues.
  • Python docs, heapq: the API, the (priority, count, task) recipe, and the 3.14 max-heap functions.
  • .NET docs, PriorityQueue<TElement,TPriority>: min-heap semantics, no stability guarantee, custom comparers.
Section titled “Related”
Sorted containers and bisectWhen you need order and removal, not just the minimum.
Shortest pathsDijkstra: a priority queue over the frontier.
Scheduling and task queuesPriority queues keyed on time or priority.
Sorting and custom comparatorsComparators and tie-breaks carry straight over to heaps.