🧩 Data Structures & Algorithms · Chapter 14

Heaps and priority queues

A heap never fully sorts anything. It just keeps the smallest item on top — and that lazy promise is exactly what schedulers, maps and top-10 lists need.

Study this lesson free in the app →

The basics

A heap is a binary tree stored in an array where every parent is smaller than or equal to its children (a min-heap; a max-heap flips it). A priority queue is the job it does: add items with a priority, and always remove the most urgent one next.

The problem it solves: you keep needing "the smallest so far" while new items keep arriving. A sorted list gives the minimum instantly but costs O(n) per insert; an unsorted list inserts in O(1) but costs O(n) to find the minimum. A heap does both in O(log n), and peeking at the minimum is O(1).

The mental model: a hospital emergency room. Patients don't queue by arrival; the most urgent is always seen next. Nobody sorts the whole waiting room — the staff just make sure the most urgent person is at the front.

Explained

Your phone's map app finds the fastest route by repeatedly asking: "Of all the places I can reach, which is closest right now?" — millions of times.

Ask that of an unsorted list and each answer costs O(n). Ask a heap and it costs O(log n): for a million candidates, about 20 steps instead of a million.

The emergency room

Patients arrive in any order: a sprained ankle, a broken arm, a heart attack, a cough.

The nurse doesn't sort the whole waiting room every time someone walks in. She keeps one promise: the most urgent patient is always at the front. When a new patient arrives, she compares them with whoever they'd displace and moves them up only as far as needed. When the doctor takes the front patient, the next most urgent steps forward after a few quick comparisons.

The ankle and the cough might sit in any order behind the front — nobody cares until they're next. That partial order is a heap. Full sorting would be wasted work.

A tree that lives in an array

index:   0  1  2  3  4  5
array: [ 1, 3, 2, 5, 9, 8 ]

            1          ← index 0: always the minimum
          /   \
         3     2
        / \   /
       5   9 8

Node i has children 2i+1 and 2i+2, parent (i−1)//2. The tree is complete, so there are no gaps and height is ⌊log₂ n⌋.

Push (O(log n)): append at the end, then sift up — swap with the parent while smaller. Pop (O(log n)): take index 0, move the last element to the root, then sift down — swap with the smaller child while bigger than it. Peek: heap[0], O(1).

Only parent–child order is guaranteed. 3 and 2 are siblings in either order; 9 is a leaf even though it's larger than 8's parent.

Six inserts, two extracts

Watch 1 climb from the bottom to the root in two swaps, and 2 climb one level. Then extract removes 1: the last item (8) jumps to the root and sinks below its smaller child. The array ends as [3, 5, 8, 9] — a valid heap, but not sorted order in general.

A priority queue at work

Think of the numbers as urgency levels (1 = most urgent). Extracts return 4, then 2, then 5 — always the most urgent item present at that moment, even though 2 arrived after 4 was served. That's the difference from a plain queue, which would serve strictly by arrival.

heapq in practice

import heapq

h = [5, 3, 8, 1, 9, 2]
heapq.heapify(h)          # O(n) → [1, 3, 2, 5, 9, 8]
heapq.heappush(h, 4)      # O(log n)
heapq.heappop(h)          # 1, O(log n)
h[0]                      # 2 — peek, O(1)

# Max-heap: negate
mx = []
for x in [5, 3, 8]:
    heapq.heappush(mx, -x)
-mx[0]                    # 8

# Priority queue of tasks; the counter breaks ties so
# two tasks are never compared directly
tasks, n = [], 0
for prio, name in [(2, "email"), (1, "outage"), (2, "report")]:
    heapq.heappush(tasks, (prio, n, name)); n += 1
heapq.heappop(tasks)[2]   # 'outage'

# Top-k largest in O(n log k), O(k) memory
def top_k(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)  # evict the smallest of the k+1
    return sorted(h, reverse=True)

top_k([4, 1, 9, 7, 3, 8], 3)  # [9, 8, 7]

What it costs, and where it's used

operation            binary heap   sorted array   unsorted array
─────────────────────────────────────────────────────────────
peek min             O(1)          O(1)           O(n)
insert               O(log n)      O(n)           O(1)
extract min          O(log n)      O(1)*          O(n)
build from n items   O(n)          O(n log n)     O(1)
search any value     O(n)          O(log n)       O(n)

\* if the minimum is kept at the end.

Why heapify is O(n): half the nodes are leaves and never move; a quarter move at most 1 level; an eighth at most 2… The sum n/4·1 + n/8·2 + n/16·3 + … stays below n.

Where heaps run: Dijkstra's shortest paths and A* (map routing), OS and job schedulers, event simulation, merging k sorted files (O(N log k)), top-k dashboards, the running median of a stream (two heaps).

Gotchas

• Thinking the array is sorted — [1, 3, 2, 5, 9, 8] is a valid heap. Iterating a heap does not give sorted order; pop repeatedly for that (heap sort, O(n log n)).
• Swapping with the wrong child on sift down — swap with the smaller child, or the bigger one ends up above its sibling.
• heapq has no max-heap API — negate numbers, or push (-priority, item).
• Comparing payloads on ties — (2, task_a) vs (2, task_b) compares the tasks and can raise TypeError; add a counter.
• Updating a priority in place — breaks the heap. Push a new entry and skip stale ones when popped (lazy deletion).
• Top-k with the wrong heap — for the k largest, keep a min-heap of size k, so the root is the smallest of the winners and easy to evict.

Words to know

In two minutes

• A min-heap is a complete binary tree in an array where every parent ≤ its children, so the minimum is always at index 0.
• Peek O(1). Insert: append, then sift up — O(log n). Extract-min: move the last item to the root, sift down — O(log n). Space O(n).
• Children of i are 2i+1 and 2i+2, parent is (i−1)//2 — no pointers needed.
• Heapify builds a heap from n items in O(n), not O(n log n), because most nodes are near the bottom and barely move.
• A heap is not sorted: searching for an arbitrary value is O(n). It only answers 'what's the smallest?' fast.
• Top-k largest of n items: keep a min-heap of size k → O(n log k) time, O(k) space. Heap sort: O(n log n), O(1) extra space, not stable.
• Python's heapq is a min-heap on a plain list; for a max-heap push negated priorities.

Test yourself

There are 8 questions, 4 puzzles and 6 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.