Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture XII of XIV

Lecture XII · Data Structures & Algorithms

Heaps and priority queues

Every queue we have built so far has been fair in the dullest possible way: first in, first out, no exceptions. That is exactly right for a print spooler and exactly wrong for an emergency room. The next patient is not the one who arrived first; it is the one who is bleeding worst. The next packet out of a router is the one carrying the video call, not the one carrying somebody’s overnight backup. The next task an operating system runs is the one with the highest priority, and the task with the lowest priority may wait all afternoon.

So we want a queue where the item you get back is the most urgent one currently waiting, not the oldest. That is the whole idea, and it is the last major container of this course. It is also, quietly, the engine of the next two lectures: Dijkstra and Prim are both just “keep pulling the cheapest thing off a priority queue until there is nothing left.”

The Priority Queue ADT

As always, we write the contract before we write a line of implementation. A priority queue stores items, each with a priority (a number, where smaller means more urgent, by convention), and supports three operations:

  • insert(item, priority) puts an item in.
  • findmin() returns the item of lowest priority value, without removing it.
  • removemin() removes and returns that same item.

That is it. Notice what is not in the contract. There is no get(i), no way to ask for the third-most urgent item, no iteration in sorted order, no searching. You may put things in, and you may take out the single most urgent thing. Everything in this lecture flows from taking that narrowness seriously, because it is precisely the narrowness that buys us the speed.

One small design decision before we go on. Items and priorities travel together, so we bundle them into a little record:

class Entry:
    def __init__(self, item, priority):
        self.item = item
        self.priority = priority

    def __lt__(self, other):
        return self.priority < other.priority

Defining __lt__ means Python’s own comparison machinery does the right thing on entries, and the rest of the code can just say a < b without repeating .priority everywhere. For most of this lecture I will drop the entries and store bare numbers, so the pictures stay uncluttered; every algorithm is identical either way, and the last section puts the entries back when we need them.

Two obvious implementations, and why each one loses

Before inventing anything, try the two structures we already have.

An unsorted list. insert is L.append(item), which is O(1)O(1) and about as fast as a computer does anything. But findmin has to scan the whole list to find the smallest, which is O(n)O(n), and removemin scans and then deletes, which is O(n)O(n) too. Cheap in, expensive out.

A sorted list. Keep the list in order at all times. Now findmin is O(1)O(1) (it is at one end) and removemin is O(1)O(1) if you keep the smallest at the back and pop from there. But insert has to find the right position and shift everything after it, which is O(n)O(n). Expensive in, cheap out.

OperationUnsorted listSorted listWhat we want
insertO(1)O(1)O(n)O(n)fast
findminO(n)O(n)O(1)O(1)fast
removeminO(n)O(n)O(1)O(1)fast
nn inserts then nn removeminsO(n2)O(n^2)O(n2)O(n^2)better than O(n2)O(n^2)

Look at the bottom row, because it is the one that matters. A priority queue is almost never used for a single operation; it is used in a loop, where things go in and come out thousands of times. Both obvious implementations give you quadratic total work, and they give it to you for opposite reasons. One pays on the way in, the other on the way out, and neither of them wins.

Here is the diagnosis, and it is worth stating as a principle. The sorted list is doing too much work. It maintains a total order on all nn items: it knows the 1st smallest, the 2nd, the 17th, all of them, at all times. We asked for one thing, the minimum, and we are paying to maintain answers to nn questions. The unsorted list is at the opposite extreme: it maintains no order at all, so it has to rediscover the answer from scratch every time.

The right structure lives between those two. Keep some order, enough to know where the minimum is, and no more than that. The question is what “some order” should mean, and the answer is one of the prettiest definitions in this course.

The heap property: just enough order

A min-heap is a binary tree in which every node’s value is less than or equal to the values of both of its children. That is the entire order requirement, and it is called the heap property.

Read it again and notice how weak it is. It says nothing about the relationship between siblings; a left child of 8 and a right child of 3 are perfectly happy together. It says nothing about the relationship between cousins, or between nodes in different subtrees. It is a purely local, parent-to-child promise, repeated everywhere.

But it has one global consequence, and it is the only one we need: the minimum is at the root. Walk down from any node and values only ever grow or stay equal, so nothing anywhere in the tree can be smaller than the value at the top. findmin is therefore “look at the root”, O(1)O(1), without maintaining a total order on anything.

A sorted list satisfies a much stronger condition than the heap property, which is exactly why it costs so much to maintain. A heap satisfies the weakest condition that still answers our one question, which is exactly why it is cheap. This is a pattern worth carrying out of the course: the cost of a data structure is the cost of the invariant it promises to keep. Promise less, pay less.

We add one more requirement, and this one is about shape rather than order. The tree must be complete: every level is entirely full, except possibly the last, which is filled from the left with no gaps. Completeness is not needed for the heap property to make sense. It is there for two reasons. First, a complete tree of nn nodes has height exactly ⌊log⁡2n⌋\lfloor \log_2 n \rfloor, so it can never degenerate into the long spindly chain that ruined the unbalanced BST last lecture; the balance is free, guaranteed by the shape rule rather than by rotations. Second, and this is the good part, a complete tree can be stored without any tree at all.

The array-as-tree trick

Number the nodes of a complete binary tree in level order: the root is 0, the next level is 1 and 2, the next is 3, 4, 5, 6, and so on, reading left to right across each level before dropping to the next. Now write the values into a flat list in that order. The claim is that the list is the tree: every parent and child relationship can be recovered by arithmetic on the indices, and there are no node objects and no pointers anywhere.

Here is why it works. Level dd of a complete tree starts at index 2d−12^d - 1 and holds 2d2^d nodes. Suppose node ii is the kk-th node on its level, so i=2d−1+ki = 2^d - 1 + k. Its children are on level d+1d+1, which begins at index 2d+1−12^{d+1} - 1, and because every node on level dd before it contributed exactly two children, its left child is the 2k2k-th node of that level:

left(i)=2d+1−1+2k=2(2d−1+k)+1=2i+1.\text{left}(i) = 2^{d+1} - 1 + 2k = 2(2^d - 1 + k) + 1 = 2i + 1.

The right child is the one next door, 2i+22i + 2, and inverting either formula gives the parent:

parent(i)=⌊i−12⌋,\text{parent}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor,

which in Python is the delightfully short (i - 1) // 2. Those three lines are the entire data structure. No Node class, no left and right fields, no None checks at the leaves; a child “does not exist” precisely when its index runs off the end of the list.

This is why completeness earns its place in the definition. If the tree could have gaps, the level-order numbering would have holes in it, the arithmetic would break, and we would be back to storing pointers. The shape rule is what lets the tree live inside an array, and living inside an array is worth a great deal: no per-node object overhead, no chasing references across memory, and the contiguous layout that makes an array fast to walk in the first place.

python runs in your browser · first run downloads ~240 kb
Plate I Index arithmetic, out loud. Three functions and a table: for each index, its parent and both children, with the values in parentheses so you can check them against the tree you drew. The last block walks from index 8 to the root by repeated halving, which is exactly the path a sift-up would take.

Now the figure this lecture exists for. Below, the same heap is drawn twice, as a row of array cells and as a tree, and every step lights up the same indices in both pictures at once. Step through the build and watch a value swap in the tree: the two cells that trade places in the array are exactly the parent and child that trade places above. The point is not that the two views agree. The point is that there is only one view, and the tree was a way of talking about the array all along.

The array · [9, 4, 7, 1, 8, 2, 6, 3, 5] after _heapify

1
0
3
1
2
2
4
3
8
4
7
5
6
6
9
7
5
8

The same array, read as a tree

103122438475669758

One array, two pictures. The children of index i live at 2i+1 and 2i+2; the parent of index i lives at (i-1)//2. Enable JavaScript to step the build, an insert, a removemin, and a heapsort one move at a time, with the same cells lit in both views.

Plate II A dual view of the heap. Ochre is the node being worked on this instant; rose is the child or parent it is being compared with; green means the subtree rooted there is already a heap; dashed cells have fallen out of the heap's end. Press Step to move one comparison or swap at a time, or Play for 1.5 seconds a step. Build runs the bottom-up heapify; Build by inserts constructs the very same heap by dropping the nine items in one at a time and sifting each up, so the two construction strategies stand side by side with their swap and comparison tallies, and the O(n)O(n) against O(nlog⁡n)O(n \log n) gap between them stays narrow on nine items (asymptotic, so Plate IV races both on a worst-case input as nn grows). Insert sifts a new item up; Remove min swaps the root out and sifts down; Heapsort does the whole thing in place. Reduced motion jumps to the finished state.

Sift up, and insert

To insert into a heap we have two invariants to protect, and it pays to break them one at a time. Put the new item in the first free slot, that is, append it to the end of the array. The shape stays complete by construction, since appending is exactly what “fill the last level from the left” means. Only the order can be wrong, and it can only be wrong in one place: between the new item and its parent.

So fix that one place, and repeat:

def _upheap(self, i):
    L = self._L
    p = (i - 1) // 2
    if i > 0 and L[i] < L[p]:
        L[i], L[p] = L[p], L[i]
        self._upheap(p)

If the new item is smaller than its parent, swap them and continue from the parent’s index. If it is not, stop, because the heap property already holds there and the item’s new parent was already smaller than everything else below it. Each step climbs one level, and the tree is only ⌊log⁡2n⌋\lfloor \log_2 n \rfloor levels deep, so insert is O(log⁡n)O(\log n) in the worst case.

There is a subtle correctness argument hiding in that swap, and it is worth half a minute. When we exchange the new item with its parent, the parent moves down a level. Is that safe? Yes, and here is why: the old parent was already less than or equal to everything in the subtree it is moving into, because it sat directly above that subtree and the heap property held. Moving it one step down cannot break anything below it. The only thing the swap can disturb is the relationship between the risen item and its new parent, which is precisely what the next recursive call checks. Nothing else in the tree is touched, and that is why a single path of swaps suffices.

Sift down, and removemin

Removal is the same idea running in the other direction, with one bit of cleverness at the start. The minimum is at index 0, so removemin has to hand back the root and then close the hole it leaves. Promoting one of the children into the hole would be a mistake: it leaves a hole one level down, which propagates, and the tree stops being complete.

Instead, take the last item in the array, the one whose removal cannot possibly hurt the shape, and drop it into the root. Now the array is one shorter, the tree is still complete, and once again only the order is broken, and only along one path. Then sift that item down until it finds its level:

def _downheap(self, i):
    L = self._L
    n = len(L)
    left = 2 * i + 1
    right = 2 * i + 2
    if left >= n:
        return
    child = left
    if right < n and L[right] < L[child]:
        child = right
    if L[child] < L[i]:
        L[i], L[child] = L[child], L[i]
        self._downheap(child)

Two details do all the work here. First, you must compare against the smaller of the two children, not whichever one you happen to check first. Swap with the larger child and you would put a big value above a small one, breaking the very property you are repairing. Second, a node may have one child or none, and the index test left >= n is the entire “is this a leaf” check, no None in sight.

Sheehy writes _downheap a little differently, with a helper that returns the range of a node’s existing children and then min(children, key=...) to pick the smaller. That is elegant Python and worth reading; the version above is the same algorithm with the loop spelled out, which I find easier to trace by hand the first few times.

Putting it together, removemin is: read the root, move the last item into it, pop the array, and sift down. One path of the tree, so O(log⁡n)O(\log n). And findmin, of course, is return self._L[0], which is as fast as reading a variable.

python runs in your browser · first run downloads ~240 kb
Plate III The whole class, running. Nine inserts build a heap, findmin reads index 0 for free, and four removemins pull the four smallest items out in order. visualize draws the underlying array each time, so you can watch a valid heap stay valid. The last block drains what remains, which comes out sorted: your first sight of heapsort.

Look at the final line of that output. Draining a heap gives you the items in sorted order, because every removemin returns the smallest of what is left. That is not a coincidence to admire in passing; it is an entire sorting algorithm, and we will come back to it.

Building a heap from scratch, in linear time

Suppose you already have nn items in a list and you want them heaped. The obvious method is to insert them one at a time, which is nn operations at O(log⁡n)O(\log n) apiece: O(nlog⁡n)O(n \log n) total.

There is a better way, and it is the most beautiful thing in this lecture. Instead of growing the heap from the top, fix it from the bottom:

def _heapify(self):
    n = len(self._L)
    for i in range(n // 2 - 1, -1, -1):
        self._downheap(i)

That is the whole algorithm. Start at the last node that has any children at all and walk backwards to the root, sifting each one down. Every leaf is skipped entirely, because a subtree of one node is already a heap. And each _downheap(i) is legitimate precisely because we go backwards: by the time we reach index ii, both of its subtrees have already been fixed, so the single item at ii is the only thing out of place, which is exactly the situation _downheap was written to repair.

(Sheehy writes the loop as for i in reversed(range(n)), over every index rather than just the internal ones. It is correct and one character shorter to reason about; the calls on the leaves simply return immediately. Starting at n // 2 - 1 skips those no-op calls, and it makes the analysis below easier to see, because it is honest about which nodes actually do work.)

The sum, done honestly

The lazy analysis says: nn calls, each O(log⁡n)O(\log n), therefore O(nlog⁡n)O(n \log n). That bound is true. It is also badly loose, and the reason is that almost none of those calls cost log⁡n\log n.

A sift-down starting at a node of height hh (height meaning the distance down to its deepest leaf) does at most hh swaps. Now count how many nodes have each height. In a heap of nn items, at most ⌈n/2⌉\lceil n/2 \rceil nodes are leaves, with height 0; at most ⌈n/4⌉\lceil n/4 \rceil have height 1; at most ⌈n/8⌉\lceil n/8 \rceil have height 2. In general, at most ⌈n/2h+1⌉\lceil n/2^{h+1} \rceil nodes have height hh. The many nodes are cheap and the expensive nodes are few, which is the whole story in one sentence.

Total work is therefore bounded by

∑h=0⌊log⁡2n⌋⌈n2h+1⌉h  ≤  n2∑h=0∞h2h.\sum_{h=0}^{\lfloor \log_2 n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil h \;\le\; \frac{n}{2} \sum_{h=0}^{\infty} \frac{h}{2^{h}}.

And that infinite sum converges. Using ∑h≥0hxh=x/(1−x)2\sum_{h \ge 0} h x^h = x/(1-x)^2 at x=1/2x = 1/2, we get (1/2)/(1/4)=2(1/2)/(1/4) = 2, so the whole bound collapses to n2⋅2=n\frac{n}{2} \cdot 2 = n. Building a heap bottom-up is O(n)O(n): linear, not nlog⁡nn \log n.

If the generating function feels like a rabbit out of a hat, here is the same fact without it. Half the nodes are leaves and do zero work. A quarter do at most one swap. An eighth do at most two. Add those up and you get n(0⋅12+1⋅14+2⋅18+3⋅116+⋯ )n(0 \cdot \tfrac12 + 1 \cdot \tfrac14 + 2 \cdot \tfrac18 + 3 \cdot \tfrac1{16} + \cdots), a series whose terms shrink geometrically while the multipliers grow only linearly, so the geometric decay wins and the sum settles at a constant. The constant is 1. For a perfect heap of 1023 items, the exact total is 1013 swaps in the worst case, comfortably under nn, whereas nlog⁡2nn \log_2 n would be about 10,000.

Where did the loose analysis go wrong? It charged every node the cost of the root. But only one node is the root. The nlog⁡nn \log n bound treats a structure whose nodes are overwhelmingly cheap as though they were uniformly expensive. That is the general lesson: when a bound feels loose, look for a summation you have been rounding up, and do it properly.

python runs in your browser · first run downloads ~240 kb
Plate IV Two builds, counted. The same worst-case input (strictly decreasing, so every inserted item climbs as far as it can) built by n inserts and by bottom-up heapify, with the swaps divided by n in the last two columns. As n grows through the powers of two the heapify ratio settles just under 1 and stays there, exactly the bound the sum predicts; the insert ratio climbs with log⁡n\log n and never stops. This is the O(n)O(n) argument, measured.

Two footnotes on that table, both worth saying out loud. First, the flat column is not proof, it is evidence, in exactly the sense we drew in the lecture on timing: measurement can refute a claim or support it, but the summation above is what proves it. Second, the input is deliberately adversarial. Repeated insertion is only Θ(nlog⁡n)\Theta(n \log n) in the worst case; on random input it is much better than the table suggests, because a random new item usually loses its first comparison and stops. Bottom-up heapify, meanwhile, is O(n)O(n) on every input, adversarial or not, and that is the point of using it.

Changing an item’s priority

Now the operation that separates a toy heap from one you can actually put in an algorithm. In Dijkstra’s algorithm you repeatedly discover a cheaper route to a vertex that is already sitting in the priority queue, and you need to say: this item is now more urgent than I told you. That is changepriority(item, newpriority).

The heap machinery for it is easy. Change the priority in place, then repair. If the priority went down (more urgent), the item may now be smaller than its parent, so sift it up. If the priority went up, it may now be larger than a child, so sift it down. One path either way, O(log⁡n)O(\log n).

The hard part is the first three words: “change the priority in place”. In place where? Given an item, which array index is it currently living at? The heap is not sorted, it is not indexed by item, and the item has been swapped around by every sift that passed through it. A linear scan to find it is O(n)O(n), and an O(n)O(n) scan in front of an O(log⁡n)O(\log n) repair means the whole operation is O(n)O(n), which throws away everything we just built.

The fix is a second structure alongside the first: an entry finder, a dictionary from item to its current index. This is the same bargain we struck with the linked list’s stored length. Extra state, kept honest at every mutation, in exchange for a question answered in O(1)O(1) instead of O(n)O(n).

“Kept honest at every mutation” is the entire difficulty, and it is where this goes wrong in practice. Every swap in _upheap and _downheap moves two items to new indices, and the map must be updated both times. If any code path swaps without telling the map, the map starts lying, changepriority writes to the wrong slot, and you get a corrupted heap with no error message. So you do not let any code path swap on its own. You funnel every exchange through one method:

def _swap(self, i, j):
    L = self._L
    L[i], L[j] = L[j], L[i]
    self._index[L[i].item] = i
    self._index[L[j].item] = j

and then _upheap, _downheap, insert, and removemin all call _swap rather than touching L directly. That is the wrapper pattern again, one class owning its internals so it can promise things about them, and it is the reason Sheehy’s priority queue stores Entry objects instead of bare values: an entry is a stable identity the map can point at while the array shuffles underneath.

Two costs come with the map, and they should be stated rather than hidden. Items must be hashable and unique, since they are dictionary keys, and every swap now does two extra dictionary writes, so the constant factor on every heap operation goes up even for callers who never change a priority.

There is a lazier alternative that is extremely common in real code, and you should know it. Do not update anything: just push a new entry with the new priority and leave the stale one in the heap, marked or simply ignored. When a stale entry surfaces at the top, discard it and pop again. This is what people do with Python’s heapq, which offers no changepriority at all. The heap grows larger than the number of live items, so you trade memory for simplicity, and you must be careful that a stale entry is always recognisable. For many programs that trade is well worth it.

python runs in your browser · first run downloads ~240 kb
Plate V The entry finder, live. A four-task queue with an index map printed alongside the heap layout, so you can see item-to-index stay in step with the array. changepriority(backup, 1) makes the least urgent task the most urgent one; watch the map update as the entry sifts up, then read the service order. Every exchange goes through _swap, which is the only reason the map can be trusted.

Heapsort: the in-place payoff

We noticed earlier that draining a heap yields sorted output. Make that observation efficient and you get heapsort, which is genuinely lovely because it needs no second array at all.

Use a max-heap (every parent at least as large as its children, the mirror image of everything above). Then:

  1. Heapify the array in place, bottom-up. O(n)O(n).
  2. Swap the maximum at index 0 with the last slot of the heap, and shrink the heap by one. The largest item is now in its final position at the end of the array, permanently, and it is no longer part of the heap.
  3. Sift the new root down over the shrunken heap, O(log⁡n)O(\log n), and repeat.

After n−1n - 1 rounds the array is sorted ascending, and the sorted portion grew backwards from the end into exactly the space the heap gave up. Total cost: O(n)O(n) to build plus nn sift-downs at O(log⁡n)O(\log n), so O(nlog⁡n)O(n \log n) in the worst case, using O(1)O(1) extra memory. Press Heapsort on Plate II to watch the dashed sorted tail eat the heap one item per round. The plate keeps the min-heap we have used all lecture rather than flipping to a max-heap, so its output comes out descending; that is the identical algorithm seen in a mirror, and swapping every comparison turns one into the other.

That worst case is worth dwelling on. Mergesort is O(nlog⁡n)O(n \log n) too but needs O(n)O(n) scratch space. Quicksort is O(nlog⁡n)O(n \log n) on average and uses almost no extra space, but its worst case is O(n2)O(n^2) and no amount of randomization makes that impossible, only unlikely. Heapsort is the one that is O(nlog⁡n)O(n \log n) guaranteed, in place, with no randomness and no bad inputs.

So why is quicksort still the one everybody uses? Because heapsort’s memory access pattern is terrible. A sift-down jumps from index ii to 2i+12i+1, then to 4i+34i+3, striding further and further through memory and missing the cache at almost every hop, while quicksort’s partition scans sequentially and the hardware prefetcher loves it. Heapsort is also not stable: equal items can be reordered by the sifts. In practice heapsort’s best-known job is as the safety net inside hybrid sorts (introsort watches quicksort’s recursion depth and, if a bad pivot streak drives it too deep, switches to heapsort to guarantee the nlog⁡nn \log n bound). Asymptotics choose the shortlist; constants and cache behaviour choose the winner.

What it costs

OperationUnsorted listSorted listBinary heap
insertO(1)O(1)O(n)O(n)O(log⁡n)O(\log n)
findminO(n)O(n)O(1)O(1)O(1)O(1)
removeminO(n)O(n)O(1)O(1)O(log⁡n)O(\log n)
Build from nn itemsO(n)O(n)O(nlog⁡n)O(n \log n)O(n)O(n)
changepriorityO(n)O(n)O(n)O(n)O(log⁡n)O(\log n) with an index map
Extra memorynonenonenone (the array is the tree)

The heap is not the best at any single row, and that is precisely why it wins. It is second-best at insertion and second-best at removal, and in a workload where both happen nn times, O(nlog⁡n)O(n \log n) total beats O(n2)O(n^2) by a margin that grows without limit. Being uniformly good beats being excellent at one thing and hopeless at the other, whenever the loop does both.

Where you will meet this again, and it is soon: Dijkstra’s shortest paths and Prim’s minimum spanning tree are both a priority queue in a loop, which is why the next lecture can present them as one algorithm with two settings. Huffman coding builds its tree by repeatedly removing the two least frequent symbols. “Give me the kk largest of a billion things” is a heap of size kk and one pass. Merging kk sorted streams is a heap holding one item from each. Event simulation is a heap keyed by time. When you find yourself writing “and now find the smallest remaining”, stop and reach for this.

In Python, the standard library gives you heapq, which operates directly on an ordinary list: heapq.heappush, heapq.heappop, and heapq.heapify, which is the linear-time bottom-up build we derived above. It is a min-heap of bare values, so the usual idiom is to push tuples (priority, item). Use it in anger; write your own once, which is what the problems below are for.

Problems

Work these in order. The last four run their own checks; make every row green.

  1. Warm-up, on paper. Take the array [2, 7, 4, 9, 8, 5, 6]. Draw the tree it encodes. Which index holds the parent of the item at index 5, and what is its value? Which indices have no children, and what single test tells you so without drawing anything? Finally, is this array a valid min-heap? If not, name the first index (smallest index) at which the property fails.

  2. Why the obvious answers lose. In two or three sentences each, explain why an unsorted list makes removemin cost O(n)O(n) and why a sorted list makes insert cost O(n)O(n). Then answer the real question: a sorted list can answer “what is the third smallest item?” and a heap cannot. Why is that extra power a cost rather than a bonus, and what exactly are you paying for it?

  3. The sum, in your own words. Bottom-up heapify calls _downheap on roughly n/2n/2 nodes, and _downheap is O(log⁡n)O(\log n), yet the total is O(n)O(n) and not O(nlog⁡n)O(n \log n). Explain the discrepancy in a short paragraph, using the phrase “at most ⌈n/2h+1⌉\lceil n/2^{h+1} \rceil nodes have height hh”. Then say which of the two bounds is wrong, and be careful: the answer is neither.

  4. Is it a heap? Write is_heap(a), which returns True when the list a satisfies the min-heap order property and False otherwise. This is nothing but the index arithmetic, so get it exactly right: a child at index c exists only when c is less than len(a), and the property is “less than or equal”, not “less than”. Run to grade against the checks.

    The checks · run against your code

    # the empty list and a single item are heaps
    assert is_heap([]) is True
    assert is_heap([5]) is True
    # a genuine min-heap passes
    assert is_heap([1, 3, 2, 4, 8, 7, 6, 9, 5]) is True
    # a sorted list is always a heap
    assert is_heap([1, 2, 3, 4, 5, 6]) is True
    # a parent larger than its LEFT child fails
    assert is_heap([1, 3, 2, 9, 8, 7, 6, 4, 5]) is False
    # a parent larger than its RIGHT child fails
    assert is_heap([1, 3, 2, 4, 8, 7, 0]) is False
    # a descending list is as unheaped as it gets
    assert is_heap([5, 4, 3, 2, 1]) is False
    # equal keys are fine: the property is <=, not <
    assert is_heap([2, 2, 2, 2]) is True
    python runs in your browser · first run downloads ~240 kb
    Plate VI The property, as a predicate. Eight checks probe the empty list, a real heap, a sorted list (always a heap), a violation at a left child, a violation at a right child, and ties. If a row stays red, print the offending i and c before you change anything.
    Hint one

    One loop over every index i, and inside it a look at the two candidate children 2*i + 1 and 2*i + 2. Before comparing, check the child index is in range. As soon as you find a child strictly smaller than its parent, you can return False immediately; if you get all the way through, return True.

    Hint two

    You do not have to visit every index. Only indices below len(a) // 2 have any children at all, so a loop over range(len(a) // 2) suffices and every child index it computes is worth checking. Either version passes; the shorter loop is the one that shows you understood the shape.

    The solution

    Two lines of arithmetic and a range check:

    def is_heap(a):
      for i in range(len(a)):
          for c in (2 * i + 1, 2 * i + 2):
              if c < len(a) and a[c] < a[i]:
                  return False
      return True

    The tuple (2 * i + 1, 2 * i + 2) saves writing the same comparison twice, and the guard c < len(a) is the whole of “does this child exist”. Note that a sorted list passes: if the array is ascending then every parent precedes both of its children in the array, so it is automatically smaller. Every sorted list is a heap, and almost no heap is sorted, which is a compact way of saying the heap property is much weaker than total order.

  5. Sift up. Finish _upheap so that insert puts a new item in the last slot and then walks it to its rightful level. The starter gives you the class, insert, and an is_heap_list helper the checks use. Two things to be careful about: stop at the root (index 0 has no parent), and stop as soon as the parent is already smaller or equal, because going further would be work with nothing to fix. Run to grade against the checks.

    The checks · run against your code

    # one insert lands at the root
    h = Heap()
    h.insert(5)
    assert h._L == [5]
    # a larger item stays where it was appended
    h.insert(9)
    assert h._L == [5, 9]
    # a smaller item climbs past the root
    h.insert(1)
    assert h._L == [1, 9, 5]
    # nine inserts leave a valid heap
    h2 = Heap()
    for x in [9, 4, 7, 1, 8, 2, 6, 3, 5]:
        h2.insert(x)
    assert is_heap_list(h2._L)
    assert h2._L[0] == 1
    assert len(h2._L) == 9
    # the smallest item always ends up at index 0
    h3 = Heap()
    for x in [4, 3, 2, 1]:
        h3.insert(x)
    assert h3._L[0] == 1
    # a sift never loses or invents an item
    assert sorted(h2._L) == [1, 2, 3, 4, 5, 6, 7, 8, 9]
    python runs in your browser · first run downloads ~240 kb
    Plate VII One path, upward. The checks pin the exact array after three inserts, then verify that nine inserts leave a valid heap with the minimum at index 0 and nothing lost. Trace the third insert if a row stays red: the item should move exactly as far as it must and no further.
    Hint one

    Compute the parent index with (i - 1) // 2. Guard with i > 0 first, so you never look at a parent of the root. If self._L[i] is smaller than self._L[p], swap the two array entries and then repeat the whole procedure from index p.

    Hint two

    Recursion is the shortest way to write “repeat from index p”: self._upheap(p) right after the swap. A while loop works just as well, and either way the climb must end when the swap does not happen. If your run never finishes, or dies complaining about recursion depth, you are almost certainly not stopping when the parent is already smaller.

    The solution

    Four lines, of which one is the base case:

    def _upheap(self, i):
      L = self._L
      p = (i - 1) // 2
      if i > 0 and L[i] < L[p]:
          L[i], L[p] = L[p], L[i]
          self._upheap(p)

    Python evaluates i > 0 first, so the parent lookup never runs at the root; that short-circuit is doing real work. The climb visits one node per level and there are floor(log2(n)) levels, which is the whole cost argument for insert. Note the swap moves the parent down into a subtree it already dominated, so it cannot break anything below it, and the recursive call checks the only relationship that could still be wrong.

  6. Sift down, and the removal that needs it. Finish _downheap and removemin. The constructor already heapifies whatever list it is handed by calling your _downheap bottom-up, so getting _downheap right fixes two things at once. Watch the three traps: compare against the smaller child, handle a node with only a left child, and in removemin move the last item into the root rather than promoting a child. Run to grade against the checks.

    The checks · run against your code

    # the constructor heapifies whatever it is handed
    h = Heap([9, 4, 7, 1, 8, 2, 6, 3, 5])
    assert is_heap_list(h._L)
    assert h.findmin() == 1
    # removemin hands back the smallest and shrinks the heap
    assert h.removemin() == 1
    assert len(h._L) == 8
    # and what is left is still a heap
    assert is_heap_list(h._L)
    assert h.findmin() == 2
    # draining the heap gives sorted order
    rest = []
    while len(h) > 0:
        rest.append(h.removemin())
    assert rest == [2, 3, 4, 5, 6, 7, 8, 9]
    # a one-item heap empties cleanly
    g = Heap([42])
    assert g.removemin() == 42
    assert g._L == []
    # duplicates survive the round trip
    d = Heap([3, 1, 3, 1])
    out = []
    while len(d) > 0:
        out.append(d.removemin())
    assert out == [1, 1, 3, 3]
    python runs in your browser · first run downloads ~240 kb
    Plate VIII One path, downward. The checks heapify a scrambled list through the constructor, pull the minimum, verify what remains is still a heap, then drain the whole thing and demand sorted output. The one-item and duplicate cases are the ones people miss.
    Hint one

    For _downheap: compute left = 2*i + 1. If that is off the end of the list, index i is a leaf and there is nothing to do. Otherwise start with child = left, and if a right child exists and is smaller than the left one, move child to the right. Only then compare child with i.

    Hint two

    For removemin: save L[0] before you overwrite it. Then L[0] = L[-1], then L.pop() to drop the now-duplicated last slot, and only then sift from index 0. Guard the sift when the list has become empty. The order of those steps is the whole problem; do them in any other order and you either lose an item or repair a heap that still has a hole in it.

    The solution

    The sift, then the removal that leans on it:

    def removemin(self):
      L = self._L
      item = L[0]
      L[0] = L[-1]
      L.pop()
      if len(L) > 0:
          self._downheap(0)
      return item
    
    def _downheap(self, i):
      L = self._L
      n = len(L)
      left = 2 * i + 1
      right = 2 * i + 2
      if left >= n:
          return
      child = left
      if right < n and L[right] < L[child]:
          child = right
      if L[child] < L[i]:
          L[i], L[child] = L[child], L[i]
          self._downheap(child)

    Swapping with the larger child is the classic bug and it is a quiet one: the array still looks plausible, most operations still work, and the heap is simply wrong in a way that only shows up several removals later. The single-child case is the other one; a node on the boundary of the last level has a left child and no right child, and right < n is the only thing standing between you and an index error. Note also that both this and the constructor’s bottom-up loop rely on the same promise: when _downheap(i) is called, both subtrees of i are already heaps.

  7. The payoff: heapsort in place. Write heapsort(xs) so it sorts the caller’s own list ascending, using no second list, and returns that same list object. Build a max-heap over the whole array bottom-up, then repeatedly swap index 0 with the last slot of the heap, shrink the heap by one, and sift the new root down. The starter sketches sift_down(i, size), which must confine itself to a[0:size]. Run to grade against the checks.

    The checks · run against your code

    # the empty and one-item cases
    assert heapsort([]) == []
    assert heapsort([7]) == [7]
    # a scrambled list comes out ascending
    assert heapsort([5, 1, 4, 1, 5, 9, 2, 6]) == [1, 1, 2, 4, 5, 5, 6, 9]
    # already sorted stays sorted
    assert heapsort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5]
    # reversed input is no harder
    assert heapsort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
    # it sorts IN PLACE: the caller's own list is the one that changes
    xs = [3, 1, 2]
    out = heapsort(xs)
    assert xs == [1, 2, 3]
    assert out is xs
    # no item is lost or invented on a longer input
    big = [17, 4, 4, 23, 0, 9, 9, 1, 12, 8, 8, 3]
    assert heapsort(list(big)) == sorted(big)
    python runs in your browser · first run downloads ~240 kb
    Plate IX Sorting with no scratch space. The checks cover the empty and one-item cases, a scrambled list with duplicates, already-sorted and reversed input, and the in-place contract: the caller's list must be the one that changes, and the return value must be that same object. Trace the first two rounds if the tail comes out wrong.
    Hint one

    A max-heap is the min-heap with every comparison flipped: inside sift_down, pick the larger child and swap when that child is greater than the parent. The size parameter is what keeps the sift out of the sorted tail: every child index must be less than size, not less than len(a).

    Hint two

    The build phase is for i in range(n // 2 - 1, -1, -1): sift_down(i, n) . The sort phase runs end from n - 1 down to 1, swapping a[0] with a[end] and then calling sift_down(0, end) , which is exactly the shrink: the item just parked at a[end] is outside the heap from that moment on. Finish by returning a, which is xs, so the in-place check passes.

    The solution

    Two phases and one helper:

    def heapsort(xs):
      a = xs
      n = len(a)
    
      def sift_down(i, size):
          while True:
              left = 2 * i + 1
              right = 2 * i + 2
              if left >= size:
                  return
              child = left
              if right < size and a[right] > a[child]:
                  child = right
              if a[child] <= a[i]:
                  return
              a[i], a[child] = a[child], a[i]
              i = child
    
      for i in range(n // 2 - 1, -1, -1):
          sift_down(i, n)
      for end in range(n - 1, 0, -1):
          a[0], a[end] = a[end], a[0]
          sift_down(0, end)
      return a

    Count the extra memory: three integers and a couple of names. That is the whole point of heapsort, and it is why it survives as the fallback inside hybrid sorts even though quicksort usually beats it on the clock. The two phases are O(n)O(n) and O(nlog⁡n)O(n \log n) respectively, so the total is O(nlog⁡n)O(n \log n) in the worst case, guaranteed, with no pivots to get unlucky with. If your reversed-input check fails but the scrambled one passes, look at the build loop: on a descending array every internal node needs sifting, and starting the loop at the wrong index quietly skips the first one.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.