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 and about as
fast as a computer does anything. But findmin has to scan the whole list to
find the smallest, which is , and removemin scans and then deletes,
which is too. Cheap in, expensive out.
A sorted list. Keep the list in order at all times. Now findmin is
(it is at one end) and removemin is 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 . Expensive in, cheap out.
| Operation | Unsorted list | Sorted list | What we want |
|---|---|---|---|
insert | fast | ||
findmin | fast | ||
removemin | fast | ||
| inserts then removemins | better than |
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 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 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”, , 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 nodes has height exactly , 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 of a complete tree starts at index and holds nodes. Suppose node is the -th node on its level, so . Its children are on level , which begins at index , and because every node on level before it contributed exactly two children, its left child is the -th node of that level:
The right child is the one next door, , and inverting either formula gives the parent:
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.
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
The same array, read as a tree
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.
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
levels deep, so insert is 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 . And
findmin, of course, is return self._L[0], which is as fast as reading a
variable.
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 items in a list and you want them heaped. The obvious method is to insert them one at a time, which is operations at apiece: 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 , both of its subtrees have already been fixed, so the single
item at 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: calls, each , therefore . That bound is true. It is also badly loose, and the reason is that almost none of those calls cost .
A sift-down starting at a node of height (height meaning the distance down to its deepest leaf) does at most swaps. Now count how many nodes have each height. In a heap of items, at most nodes are leaves, with height 0; at most have height 1; at most have height 2. In general, at most nodes have height . 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
And that infinite sum converges. Using at , we get , so the whole bound collapses to . Building a heap bottom-up is : linear, not .
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 , 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 , whereas 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 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.
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 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 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, .
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 , and an scan in front of an repair means the whole operation is , 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 instead of .
“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.
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:
- Heapify the array in place, bottom-up. .
- 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.
- Sift the new root down over the shrunken heap, , and repeat.
After 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: to build plus sift-downs at , so in the worst case, using 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 too but needs scratch space. Quicksort is on average and uses almost no extra space, but its worst case is and no amount of randomization makes that impossible, only unlikely. Heapsort is the one that is 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 to , then to , 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 bound). Asymptotics choose the shortlist; constants and cache behaviour choose the winner.
What it costs
| Operation | Unsorted list | Sorted list | Binary heap |
|---|---|---|---|
insert | |||
findmin | |||
removemin | |||
| Build from items | |||
changepriority | with an index map | ||
| Extra memory | none | none | none (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 times, total beats 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 largest of a billion things” is a heap of size and one pass. Merging 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.
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.Why the obvious answers lose. In two or three sentences each, explain why an unsorted list makes
removemincost and why a sorted list makesinsertcost . 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?The sum, in your own words. Bottom-up heapify calls
_downheapon roughly nodes, and_downheapis , yet the total is and not . Explain the discrepancy in a short paragraph, using the phrase “at most nodes have height ”. Then say which of the two bounds is wrong, and be careful: the answer is neither.Is it a heap? Write
is_heap(a), which returnsTruewhen the listasatisfies the min-heap order property andFalseotherwise. This is nothing but the index arithmetic, so get it exactly right: a child at indexcexists only whencis less thanlen(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 kbPlate 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 children2*i + 1and2*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 returnFalseimmediately; if you get all the way through, returnTrue.Hint two
You do not have to visit every index. Only indices below
len(a) // 2have any children at all, so a loop overrange(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 TrueThe tuple
(2 * i + 1, 2 * i + 2)saves writing the same comparison twice, and the guardc < 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.Sift up. Finish
_upheapso thatinsertputs a new item in the last slot and then walks it to its rightful level. The starter gives you the class,insert, and anis_heap_listhelper 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 kbPlate 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 withi > 0first, so you never look at a parent of the root. Ifself._L[i]is smaller thanself._L[p], swap the two array entries and then repeat the whole procedure from indexp.Hint two
Recursion is the shortest way to write “repeat from index
p”:self._upheap(p)right after the swap. Awhileloop 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 > 0first, 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 arefloor(log2(n))levels, which is the whole cost argument forinsert. 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.Sift down, and the removal that needs it. Finish
_downheapandremovemin. The constructor already heapifies whatever list it is handed by calling your_downheapbottom-up, so getting_downheapright fixes two things at once. Watch the three traps: compare against the smaller child, handle a node with only a left child, and inremoveminmove 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 kbPlate 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: computeleft = 2*i + 1. If that is off the end of the list, indexiis a leaf and there is nothing to do. Otherwise start withchild = left, and if a right child exists and is smaller than the left one, movechildto the right. Only then comparechildwithi.Hint two
For
removemin: saveL[0]before you overwrite it. ThenL[0] = L[-1], thenL.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 < nis 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 ofiare already heaps.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 sketchessift_down(i, size), which must confine itself toa[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 kbPlate 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. Thesizeparameter is what keeps the sift out of the sorted tail: every child index must be less thansize, not less thanlen(a).Hint two
The build phase is
for i in range(n // 2 - 1, -1, -1): sift_down(i, n). The sort phase runsendfromn - 1down to 1, swappinga[0]witha[end]and then callingsift_down(0, end), which is exactly the shrink: the item just parked ata[end]is outside the heap from that moment on. Finish by returninga, which isxs, 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 aCount 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 and respectively, so the total is 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.