10Priority Queues & Heaps — Promise Less, and Keep It

01The ask was "next"

Watch what a build farm actually asks its queue: not the order of three thousand jobs, only which one runs next.

Count the asks on a real afternoon. A machine frees up, and the farm asks once. Forty machines free up a few hundred times an hour, so the farm asks a few hundred times. Developers keep submitting all day, which means the three thousand is never the same three thousand for two asks running. Nobody, at any point in that afternoon, reads job number 1,741 of the order. Nobody reads job two. The only position anyone ever consults is the front.

English is partly to blame for how strange that sounds. It hands one word — order — to two different things: the arrangement of the whole, and which one comes next. Every explanation of today's tool opens with the phrase "a partially ordered tree", and a learner hears a slightly worse sorted array. This page starts from the other end. Start from what was actually asked, because the ask was next.

There is a harder case than an arriving queue, and it is the one that settles the point. A discrete-event simulator models a network by handling its next event, and handling that event schedules three more at computed future times. Read that again with a one-time arrangement of the whole in mind. You cannot arrange what handling the front has not created yet. Arranging everything up front is not slow here. It is impossible, because processing the top item is what creates the items after it.

A hospital triage board runs the same shape at a slower clock. Treating the most urgent patient changes who is now most urgent, and the doors do not close while anyone deliberates. A build farm, a simulator, a triage board: three rooms, one ask. In all three, the set is still being made by the very act of consuming it. The full order of such a set is not expensive to compute. It does not exist, because there is never a moment when the set is finished and could hold one.

So the question this page prices is smaller than the one page 8 answered, and the size of that gap is the whole subject ahead. An arrangement that delivers the front, and only the front, promises far less than one that delivers every position at once. What the smaller promise costs to keep, and what keeping it lets the set do — arrive, one item at a time, without end — occupies every section below. From this one, hold only the shape of the ask.

One piece of fine print gets named now, while the asking is still fresh. The farm's answer is honest in a particular sense: its front is the earliest job that has shown up. For the simulator those are the same thing, because every event it schedules lies in its own future, so nothing created later can be due earlier. The simulator earns its front by construction. A queue whose producers stamp their own due times earns no such thing, and a late arrival can carry an earlier key than the front you just served — served correctly, by an arrangement keeping its promise, and wrong anyway. Write that condition down now, because a room near the end of this page will collect on it: the front is the true next only when nothing still to arrive can carry a smaller key.

02A promise has a size

Before pricing the weaker promise, count the one page 8 sold you, because "the order" is a phrase with a number inside it. A sorted array of eight entries looks like one fact, a single tidy arrangement. It is actually a stack of claims about pairs: point at any two entries, and the arrangement already knows which is smaller. Point at the third and the seventh, and sorted answers without comparing, because that answer was folded in at build time. Page 8 called sorted an invariant with upkeep, and an invariant is a promise — this one can be counted pair by pair. So the honest first question is not how fast the sort ran. It is how many pairs of eight items the arrangement stands behind.

Write your count down before reading on — an actual number, on paper — because a count you named gets corrected in a way a handed count never is. Fig. 1 below keeps two claim-sheets side by side, one for the total order and one for the promise "the front is smallest". Every pair each arrangement stands behind is laid out row by row, with what it entailed and what it paid totalled at the foot. Read your number against the sheet, row by row. Nothing marks it wrong. It is counted against, which is better and worse at once.

Count the left column the way the figure does, row by row. The first entry stands in a pair with each of the other seven, so it enters seven claims. The second adds six pairs nobody has counted yet, and the third adds five. Each row shrinks by one until the last entry adds nothing new. The column reads 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28, and the closed form C(8,2) = 8·7/2 = 28 agrees with the count. Twenty-eight pair-claims is what a total order on eight items entails. Now read the second line, the one recording what the sort paid. Eight items can arrive in 8! = 40,320 possible orders, and log₂ 40,320 ≈ 15.3. So page 3's floor prices any sort of eight at sixteen comparisons or more. A sort exists that pays exactly 16 on eight items, so "about sixteen" is arithmetic, not a courtesy. Sixteen comparisons bought twenty-eight claims. The twelve-claim surplus has a name: transitivity. Prove a below b and b below c, and a-below-c arrives free — an entailed claim no comparison ever paid for.

"The front is smallest" is a claim about the front against each of the other seven, and about no other pair at all. So the weak promise entails exactly 7. Finding the minimum of eight costs exactly 8 − 1 = 7 comparisons, one per rival, so it also pays 7. Every claim in that ledger was bought directly, and transitivity handed over nothing, because nothing sits downstream of "smallest" to derive. Now set the two columns beside each other and read the gaps separately. 28 entailed against 7 entailed is the guarantee gap, four to one on eight items. 16 paid against 7 paid is merely the bill. The bill is not the unit this section is pricing.

The adjectives finally have a unit. "Partial" and "total" arrived as vocabulary, and vocabulary cannot make weaker mean anything except worse. Counted, the words turn into sizes: a total order on n items entails C(n,2) claims, and the front-is-smallest promise entails n − 1. A smaller guarantee is not a damaged big one, it is a different purchase. Do not let the two ledgers blur: 16 paid and 28 entailed describe the same sorted array and answer different questions. Hold the two ledgers apart — what an arrangement entails and what it paid. A section further down will turn that exact separation into the most surprising number on this page.

03The weakest claim that still names the front

Here is the entire rule: no child beats its parent, and about every other pair the arrangement says nothing at all. That sentence sounds too thin to hold ten keys in any shape, so count what it actually claims. Every node except the root has exactly one parent. Ten keys therefore carry exactly 10 − 1 = 9 parent-child claims, a number read off the budget rather than invented. Set that beside the last section's ledger. A total order over the same ten keys entails 10 × 9 / 2 = 45 pair-claims. This arrangement makes nine claims and stays silent on the other thirty-six.

The trouble is that nobody hears the rule at its stated size. A rule about a pair gets silently upgraded to a rule about a level: siblings feel ordered left to right, and level 3 feels entirely larger than level 2. The upgrade is comfortable, and it matches every clean diagram you have ever seen. No drawn example has ever contradicted it, because a tidy example satisfies both readings at once. A belief that survives every picture can only be tested by a picture built to press on it.

Fig. 2 below holds ten keys in a complete tree, and one detail is arranged to press on the upgrade directly. A 9 sits at depth 3, near the bottom. A 40 sits at depth 1 in the other subtree, two levels above it. The figure asks one question and withholds everything else: is this arrangement legal? Call it before the check runs, because the nine claim-edges sit grey and unchecked until you do. Whatever you answer, the reveal walks the nine claims one at a time, and you watch which pairs the rule ever mentions.

Watch what the walk never visits. The 9-below-40 pair is not among the nine, because no comparison was ever purchased across those two subtrees. 2 ≤ 5, then 2 ≤ 40, then 5 ≤ 8 and onward. Every checked edge joins a parent to its own child. Not one edge joins a level to a level. The rule was always about pairs, exactly the 10 − 1 = 9 edges the budget allowed, and depth never entered it. The level upgrade was comfortable, it matched every clean diagram, and it is false. If you called the picture wrong, good. Being wrong in front of the picture is the one cure this particular belief admits.

What the nine claims add up to is a promise with a direction. Each node bounds its entire subtree from below, and it bounds nothing else anywhere. Downward the claims chain: 2 ≤ 5 and 5 ≤ 8 give 2 ≤ 8. That same chaining down every path is why the root holds the smallest of all ten (the one global fact ever delivered). Sideways there is no chain to follow. The 9 and the 40 share nothing but an ancestor, and an ancestor sits below both of them, saying nothing about the space between.

So read this arrangement's quiet the way you would read a contract's. Nine claims were paid for, and nine are kept under every arrival still to come. Everything else on this page follows from the thirty-six that were never bought. Some of it is cost, and the honest half ahead will price it without flinching. Some of it is the strangest discount in the chapter. The silence between siblings is not a defect the design tolerates; the silence is the product, and the rest of this page is what that silence costs and what it buys back.

04One doubt, one path

Page 5 sank one entry through three levels, priced the walk at lg 8 = 3, and asked you to take the sink on trust; here is what was owed. The debt was never the number, because page 5 paid that number in full. What page 5 could not say is why the repair is a path and not a search. Break one node in a heap of a million and instinct reaches for page 2's recurrences. A million nodes sounds like a million places the damage could hide. It cannot hide anywhere. Watch where the doubt is allowed to live.

Put one wrong node in front of you and count the doubt. Take the ten-key heap from the last section and replace its root with a worse key. Both subtrees below it are still legal heaps, because you touched neither. The rule was n−1 parent-child claims, and this edit disturbed at most two of them. The new key stands accused against its left child, and against its right. Every other claim in the building still holds, untouched. Two pairs in doubt, out of the nine claims the ten-key heap ever made — that count is the entire theory of the repair.

Now swap the wrong key with the smaller of its two children. The smaller child sits on top, so it beats its sibling and everything under its sibling from above, and the claims inside both subtrees were never touched. Look at what remains. One node possibly wrong, both subtrees under it legal — the identical question, sitting one level down. Nothing branched. The doubt had one place to go, and it went there.

Read page 5's lg 8 = 3 again with that picture in hand. The walk visits one node per level, and page 5's eight-item tree has three levels under its root. So page 5's lg 8 = 3 is a ceiling on how far one doubt can travel. The logarithm is confirmation, never news. You did not derive it from a size-shaped recurrence, because nothing ever split into halves to recurse on. You watched a height-shaped fact and read the height off the tree.

Raise a key instead of lowering one and the picture flips exactly. The pair in doubt is now above you — the changed node against its one parent — so the same swap carries the doubt up instead of down. Check the parent, swap if it loses, and the identical question sits one level higher. One doubt, one path, in either direction, and the root or a leaf is where the path runs out.

Hold this against the closest neighbour it has, because page 8 also kept an order alive while items arrived. Page 8's upkeep was the merge: a pass over the whole file, paid once per batch. It is cheap per item because the surviving order does the work. This upkeep is cheap for the opposite reason. There was almost no order to keep, because n−1 claims is all there ever was. So the bill is one path, paid at each arrival, while the item is still in your hand. "Still arriving" means two different things on the two pages — page 8 can absorb a nightly batch, and only this arrangement can absorb an item at a time.

05A tree with no pointers

Draw the tree the obvious way, three pointers to a node. A million items make a tree twenty levels deep, because lg 1,048,576 = 20 counts its levels. The longest repair walk is therefore nineteen hops, root to floor. Each hop is the machine fetching a pointer, chasing it to wherever the allocator dropped the child, and starting over. That is a fetch nothing could have guessed. So each hop pays page 7's cold price of 80 ns, not the warm 14 ns a lucky cache could hand back. Nineteen hops at eighty nanoseconds is about 1,500 nanoseconds of pure waiting. Then add the rent. Two child pointers and one parent pointer are twenty-four bytes of bookkeeping around an eight-byte key, so three quarters of every node is directions to other nodes.

Now watch what the repair walk actually asks for. A sinking entry compares against two children and swaps with one. A rising entry compares against one parent. That is the whole shopping list, ever. So number the nodes level by level, root first, left to right, and the list turns into arithmetic: the children of slot i live at 2i and 2i+1, and its parent lives at ⌊i/2⌋. Slot 4's children sit at 8 and 9, its parent sits at 2, and nobody stored any of that anywhere. Page 8 sold you position is an address once already. Here the same coin is cashed a second way, because the position now encodes the family relation itself.

The trick carries a precondition, and the precondition is the shape. The arithmetic only lands on real nodes when the tree is gapless — every level full, the last filled from the left with no holes. A heap can promise that shape precisely because it promises so little else. No key cares where it sits, only that no child beats its parent, and that claim survives dropping each arrival into the slot that keeps the block solid. A search tree cannot make the same deal. Its shape follows its keys, a run of sorted inserts stretches it into a bare path, and a twenty-node path numbered this way would demand 2¹⁹ = 524,288 slots for its twenty entries. The flat layout is not a general trick for trees. It is the private reward for promising less, unavailable to anything sparse.

Count what the flat block buys back. No pointer is fetched, because no pointer exists. The child's address is one multiply on a number already sitting in a register, and multiplying by two is a one-bit shift. No node is allocated on arrival, because the next slot already exists. The slots are contiguous, so one cache line hauls in a run of neighbours together, not one stranded node from wherever the allocator left it. And the twenty-four bytes of directions are simply gone: a million eight-byte keys occupy eight megabytes flat, where the pointered tree spent thirty-two.

One worry is left, and it is the honest one. An array is born with a fixed length, and the whole reason this page exists is that items keep arriving after the structure stands. So the block will fill. A full block looks, for a moment, like the end of the flat layout and everything it bought. The array must grow while items arrive, and page 2 already settled that bill — double on overflow and each arrival stays O(1) amortised — so the flat layout keeps the one condition that justified it.

06The bill for building one from a million

You now hold every piece of the arithmetic — the gapless shape from the last section, and one repair priced at one path from the section before — so this number is yours to get wrong. The task is blunt. A million loose numbers arrive at once, and the one promise must be made to hold everywhere (no child beats its parent). The question is what that costs, all told. Not a bound handed down from a theorem. A number you compute yourself, commit to in writing, and then check against your own reason for it.

Here is the account almost everyone writes first, and every part of it is true. The tree holds 1,000,000 items, and 2²⁰ = 1,048,576 clears a million, so the tree stands twenty levels deep and no item stands more than nineteen levels off the floor. One repair sinks one node, and a sink walks at most the tree's height. A million repairs at nineteen levels apiece is 19,000,000 levels of sinking. Check each clause and each one holds. Write down whatever total you believe, but write the reason beside it, because this room grades reasons.

The build procedure is pinned before you answer, because a total means nothing until the loop is fixed. Start at the last node that has children. Sift it down. Step backwards, node by node, until the root itself has been sifted and the promise holds everywhere. Fig. 3 asks for your total and a one-line reason, and the commit stays shut until both exist. The reason matters more than the digits, because the reveal corrects reasons. Commit, and two charging columns fill under your hand, row by row, until you can see which account was yours.

Column A is the account from two paragraphs ago, and it charges every node the tree's height: 1,000,000 nodes at 19 levels each is 19,000,000. Column B charges each node its own height, and the census does the rest. In the idealised halving census, 500,000 leaves sit at height 0 and pay nothing. Then 250,000 nodes at height 1 pay 250,000 levels, and 125,000 nodes at height 2 pay 250,000 more. The column peaks right there, at heights 1 and 2. Then 62,500 nodes at height 3 pay 187,500, and 31,250 nodes at height 4 pay 125,000 — a running total of 812,500 after five rows. Each row is now visibly smaller than the one before it, while the price steps up only by one. At the top of the building, one node at height 19 pays 19. The total lands near 1,000,000 — about one level per item. The footnote's algebra, Σ h/2^h = 2, only confirms what the column already showed by stopping.

Watch what actually happened, because it is a fact about promises before it is a fact about sums. Half the nodes are leaves, and a leaf is a node about which this arrangement promises nothing at all. You are not paying for the leaves because you never bought them. The reason you wrote was never wrong, it was loose. "A million sinks, each at most nineteen levels" is a correct upper bound that charges every node the most expensive price in the building. The true race is between a census that halves and a price that grows by one, and the census wins. That counting move travels with its hypothesis attached: in any tree whose node count halves as you climb, a per-node cost equal to that node's own height sums to linear. Skew the same nodes into a path and the identical sum goes quadratic, 0 + 1 + … + (n−1).

Say the page 2 word now, so nobody reaches for it. Nothing here is amortised. No potential fund was filled, no cheap operation subsidised an expensive one, and no charge was moved from the step where it happened. Every node's charge is its actual cost, and the total is just the sum. Twenty million failed for a different reason than an average fails. It charged flat rate for a building that is mostly ground floor.

Fig. 3's second beat is the counterweight, and it earns the contrast honestly. Feed the same million by successive inserts, with the arrivals pinned to decreasing order. Every insert is the new minimum, so every insert floats to the root, paying its depth. Depth is the census run the other way: the largest crowd of the million, 475,713 nodes, sits at depth 19, where the price is largest. The depths across the million sum to 17,951,445 levels of floating — call it eighteen million against the build's one million. And the two methods produce different arrays from the same input, both legal. The claim was always same promise, never same arrangement.

Two honesty notes, so the contrast is not oversold. Shuffle the arrivals — page 4's habit, take the order away from the adversary — and the same insert loop averages a couple of levels per item, Θ(n) expected. The eighteen million was the adversary's number, not the loop's. Second, both columns charge one unit per level walked, and that is a labelled simplification. Counted in comparisons, a sink pays two per level (pick the winning child, then test it against the parent) and a float pays one. So the build pays about 2,000,000 comparisons and the adversarial insert loop about 18,000,000, and the contrast narrows from roughly eighteen-to-one in levels to roughly nine-to-one in comparisons. The lesson does not move at all.

Fig. 3 closes with the fifteen-item check, both ways, ninety seconds by hand. Fifteen nodes make a complete tree: eight leaves at height 0, four at height 1, two at height 2, one at height 3. The heights sum to 4·1 + 2·2 + 1·3 = 11. The depths sum to 1·0 + 2·1 + 4·2 + 8·3 = 34, three times the bill for the same fifteen items. Nothing here was amortised, no cheap operation subsidised an expensive one, and that is why the question travels: did I charge each item its actual cost, or the most expensive price in the building?

07What it refuses to know

Now the honest half, because contains() is right there on the collection, it compiles, it returns the right answer, and it costs a full scan with nothing complaining. Every price so far on this page was the cost of something the arrangement does well. This one is the cost of asking it something it never agreed to know. Membership is Θ(n) — in the worst case the probe visits every node in the tree. And the reason is worth getting exactly right, because the reason most people carry is false.

The folklore says a heap cannot prune at all, and the folklore is wrong. The promise is one-directional: a node’s key bounds its whole subtree from below. So a probe hunting for 40 at a node holding 57 can rule that entire subtree out. That pruning is real, and it is exactly what Frederickson’s O(k) selection algorithm spends to find the k smallest without popping. What no probe can ever do is rule the other child in. Both children can sit at or below the key you want, so every step keeps both branches alive. The branching never collapses, and that is the whole proof: the worst case is the whole tree.

Now place the silence, because page 9 taught you a different one and the two are easy to conflate. Page 9’s silence was about the answer: a false monotonicity claim returned a clean wrong number, and nothing complained. This silence is about the bill. The answer is right. Every test passes. The cost profile is page 8’s lawn rather than a tower — thousands of small scans, never one spike — and a lawn is harder to catch in review precisely because nothing is wrong.

The second trap ships more quietly still. Print the backing array, and the first element is the minimum, because that much is promised. The rest is not the run order. But small keys sit high in a heap, so the printout looks almost sorted, and almost sorted survives eyeballing. An ops page that lists the queue this way gets approved by a reviewer who checked the top and nodded.

The repair is a pairing, and the pairing is not an apology. Keep a hash set of ids beside the heap — page 7’s finished instrument, doing the one job it is built for. Id in on every push, id out on every pop, and membership costs O(1) owned by the set, not by the heap. Resist upgrading it to id→position. That is a strictly bigger promise, and a later section on this page prices what keeping positions honestly costs.

And the rule you now hold pays out one more refusal, one sentence from where you stand. The arrangement bought exactly n−1 comparisons, one per parent-child pair, and parent-child pairs are the only pairs it ever paid for. So watch what happens when the front leaves. The root’s two former children rise into contention, and they are exactly the pair no purchased comparison ever separated. The reader who believes the ranking is in there, latent, handed out slowly, has just met the node where it is not.

Check it by hand on a knockout of eight names, because a bracket is the same purchase. Eight entrants, seven matches, one comparison each — seven claims, the heap’s n−1 exactly. The champion is sound, because every entrant lost to somebody who lost to somebody who lost to the champion. Second place is not. Seed the strongest rival into the champion’s opening match and watch what the bracket records: a first-round exit, and a final contested by somebody weaker. The runner-up of a knockout is only the best of those the champion happened to beat, and the true second best may have gone home in round one.

08Top k, audited on our own numbers

Two earlier pages promised you this room by name, and the tell is a phrase people say without noticing they have said it: from now on. Page 8 heard it inside "the top k from a set that is still arriving" and routed the sentence here. Page 9's own table routed here again. The room is small and exact. Keep the ten smallest of a million measurements while the million is still arriving, and never hold more than the ten. A sort cannot work in this room, because a sort needs a last item and a stream has none. What neither promise said is how the ten are kept, and that turns on a question with exactly two answers.

Fig. 4 opens on that question and will not move until you answer it. You will hold ten items, and an arrangement of ten sells you exactly one front, cheap to read and cheap to replace. Which end of your ten should that front be — the best thing you hold, or the worst? Commit a polarity and the stream runs. Refuse, and the status line prints that the arrangement points nowhere and the stream stays frozen at zero items. The commit is pinned and kept forever, right or wrong. Being wrong in front of a running stream is the fastest way to own the rule. So the figure keeps a wrong arrangement on screen, beside the first item it threw away.

Here is what the commit teaches, and it is one move from the last section's bracket. To keep the ten smallest you must evict on every win, and the thing you evict is the worst of your holdings, never the best. An arrangement of ten tells you the front of ten and nothing more, so the front must be the item you are willing to lose. You point the arrangement the other way: the container keeping the smallest items faces its largest one forward. Every arrival now pays one test against that front. Lose the test and the arrival never enters. Win it and the front is evicted, the arrival sifts in over about log₂ 10 ≈ 3.3 levels, and the worst of the new ten faces forward again. Point it the intuitive way instead and your front is your best item. The first thing your arrangement throws away is then the very minimum you were hired to keep.

The second thing page 8 could not say is what happens when k moves, because page 8 pinned k at ten and never touched the pin. Move it. The speedup over a full sort is the ratio log₂ n over log₂ k — both bills priced as advertised, the same pricing the next beat audits. At n = 10⁶ the top of that ratio is log₂ 10⁶ = 19.93. At k = 10 the bottom is log₂ 10 = 3.32 and the advantage is 6.0×. At k = 1,000 the bottom is log₂ 1,000 = 9.97 and the advantage is 2.0×. At k = 100,000 the bottom is log₂ 100,000 = 16.61 and the advantage is 1.2×. Your holdings, meanwhile, have climbed from ten items to a tenth of the stream. Both readouts move against the tool at once. The advantage thins exactly as what you hold stops being small, and on the dial you can watch the tool hand itself back to page 8's sort.

The third thing is a bill this page owes itself. The build count left you holding a question: did I charge each item its actual cost, or the most expensive price in the building? Turn it on our own advertisement. The advertised bill for the ten smallest of a million is n log₂ k. That is 1,000,000 arrivals times log₂ 10 = 3.3219 levels each, about 3,320,000 comparisons. Now charge actual costs, against a stream in no particular order — a hypothesis about the input, page 4's distinction, and it gets named. Almost every arrival fails its one test against the front and never enters the structure at all. Under that hypothesis the arrivals that do enter number about k·ln(n/k). For ten of a million that is 10 × ln 100,000 = 10 × 11.513, roughly 115 entries. Each entry sifts about 3.3 levels, and a sift level costs two comparisons, so all the sifting together comes to a few hundred — this stream counts 520. Every other arrival pays exactly one. The measured bill is 1,000,526 comparisons, which is n and nowhere near n log k. Feed the million in decreasing order instead and every arrival enters, so the advertised 3,320,000 is paid in full. The advertisement was loose about the stream, not the structure — and loose in the tool's favour only while nobody aims the input.

And still the comparison count is a demoted line in the figure, because comparisons were never the claim. Neither is held size the primary readout. Ten held against 1,000,000 seen is page 8's own Fig. 5. It stands here as a static banner, quoted once rather than re-earned — "keeping the ten slowest keeps ten, tonight and next year." The primary readout is the moving pin. Turn the dial and two readouts move against the tool at once. The advantage falls from 6.0× to 1.2× while the holdings climb from ten items to a tenth of the stream. That pin is priced on the two advertisements. Audit both in the third beat's manner and the advantage is larger at every k, and it slides the same way. That double slide is the claim page 8 could not make, and the polarity commit and the honest bill are the other two things it could not show.

So read the three back in one breath. The polarity was committed before the stream moved and kept whether or not it was right. The moving pin showed the advantage falling from 6.0× to 1.2× while the holdings swelled, the tool visibly handing itself back to the sort. The build count's question, aimed at our own cost model, found the real bill at n for any stream nobody aimed — a correction that flatters the tool and was made anyway. A page that audits its own advertisement is the honest half working — and the prize was never the logarithm, it was that you held ten while a million went past.

09The handle you must keep yourself

The textbook Dijkstra requires an operation your standard library refuses to ship, and the reader's first guess — blame the language — is exactly wrong. The operation is decrease-key: a settled node has revealed a cheaper route to an entry waiting inside the arrangement, and the algorithm wants that entry's key lowered where it sits. Python's heapq does not have it. Java's PriorityQueue does not have it. The C++ priority_queue does not have it. Three library teams declined the same operation independently, across three decades. A refusal that unanimous is a finding about the operation, not an oversight in any language.

Here is what they found. Lowering one entry's key means reaching that entry, and reaching it means knowing where it currently sits. But this arrangement's whole cheapness came from moving things without asking. Every repair swaps elements down one path, so an item's position changes and nobody outside is told. The structure needs the freedom to relocate anything at any moment, and the world needs stable identity — a name that still points at the same thing tomorrow. Decrease-key is the one operation that demands both at once. This is the search refusal from two sections back, wearing a work shirt. You cannot ask the arrangement where something is, because where things are is exactly what it keeps rewriting.

The obvious patch is a second structure: a map from each id to its current position, kept beside the heap. Count what keeping it true costs. The map stays true only if every swap inside every sift writes the moved element's new index back — both elements, every swap, no exceptions. One sink on a million-entry heap walks lg 1,000,000 ≈ 20 levels, so one pop can demand forty map writes. And no standard library's sift will make those writes, because the library cannot know your map exists. The map cannot be bolted on from outside. The only honest version rewrites the sift itself, and then you are not using a library, you are maintaining a fork of one.

The working escape refuses the operation entirely, and it is four lines. When a cheaper route to a waiting node appears, do not touch the old entry: push a duplicate carrying the better key, and let the worse one sit. When an entry surfaces at the front, compare its key against the best distance already recorded for that node. If the recorded number is smaller, this pop is stale. Drop it and take the next one. That is the whole mechanism — no handle, no map, no rewritten sift, and every element the arrangement quietly relocates is one nobody outside will ever ask about again.

Count the price on a real graph. A road network with 100,000 intersections carries about 250,000 segments, and the duplicate heap can grow to one entry per segment: 250,000 entries against the textbook's 100,000. That factor of 2.5 charges almost nothing. The repair path grows from lg 100,000 ≈ 17 levels to lg 250,000 ≈ 18, one level, and each stale pop dies after one comparison against a recorded distance. Set that beside the forty map writes per pop the handle demanded, and the trade explains itself. The last section showed why the good half is free: eviction happens at the front, where the promise lives. A cancel asks for the middle, which is the position the arrangement refused to sell.

One structure was built to make the refused operation cheap, and its fate is the last word this section needs. The Fibonacci heap prices decrease-key at O(1) amortised — page 2's word, spent, not re-earned — and pays for that constant by buying back every pointer the flat array escaped. On our road network its ledger reads 100,000 extract-mins against at most 250,000 decrease-keys, and the design bets on the second number dwarfing the first. On real sparse graphs it never does by enough. Fibonacci heaps were designed backwards from |V| extract-mins against |E| decrease-keys, and their own textbook calls them predominantly of theoretical interest; the four-line duplicate-and-skip is what actually runs.

10Twenty-five rooms

The words "heap" and "priority queue" appear nowhere in the twenty-five rooms below, because they never appear in the wild either. Nobody files a ticket asking for one. The ticket says three thousand jobs are queued, developers keep submitting, and the most urgent must always run next. It never says the word. The reach is recognising a shape inside a sentence that was never written for you. That recognition is the entire product of a tool page, and no list of answers can install it.

So Fig. 5 deals the rooms one at a time and makes you call each one on the sentence alone. Three of the twenty-five you have already met. The build farm, the simulator and the triage board return from the first section as the anchor; the other twenty-two were never written for you. You commit REACH or AWAY on the one-line situation, before the tell unmasks. This is page 9's grammar exactly: verdict first, evidence second, headcount last. The census strip stays masked until the last room is called. A split announced early is a hint, and you would start calling rooms to balance the count instead of reading them. Call all twenty-five, and the strip unmasks beside your own scorecard.

Fourteen of the twenty-five resolve away, and every away names a destination you can walk to. The tells transfer beyond this page. The phrase from now on, said by somebody who has not noticed saying it, is the reach that pages 8 and 9 both promised by name. Everything arrived before anything was asked walks you back to page 8, where one sort buys the whole order and stops. Pure membership with no order in the question is a hash set, id to bool and nothing more. A traversal nobody downstream reads in order is a plain stack, cheaper and with no comparator to be wrong. And a count over a range belongs to the arrival log you already own — sorted at zero upkeep, two boundary probes, forty-six in all, in page 9's manner. Three of the destinations — the wheel, the buckets, the histogram — are one move wearing three coats. Somebody chose a grid for the keys, so nobody compares anything.

Two refusals in the drill are new, and both are structures. When one sentence contains next-by-key AND lookup-by-id AND cancel-by-id, reach past the flat array to an ordered map. It keeps a total order alive under arrival too, at a logarithm's price — about fifteen comparisons per touch on twenty thousand queued jobs. The price is every pointer and every rebalance the gapless array escaped, so demand two of the three asks before paying it. And when the resolver has already computed a safe order, the answer is no structure at all. Page 5 exported that rule and it is credited here: when the structure already supplies a safe order, delete the machinery.

The k-boundary rooms audit one rule of thumb on four live values of k. Eight largest per row is a sorted array of eight, living in one cache line with nothing to mispredict. Twelve backends is a scan, because the whole axis fits on that same line. Sixty sorted files is the logarithm winning outright, one record held per file forever. And sixteen registers is the boundary made flesh: the shipped linear-scan allocators measured rather than derived, and they keep a short sorted list. Quickselect takes the last refusal (a complete set, one rank). There k grows so close to n that n log k stops differing from n log n.

One room is called correctly and can still be wrong, in a direction no structure can point. A thousand shards each report their hundred hottest keys, and the bounded arrangement of one hundred over the merged reports is correct. But if hotness were a count summed across shards, the local top hundreds would not contain the answer at all. A key ranked 101st everywhere beats one ranked first somewhere, and appears in no report. The arrangement is right and the input is wrong, and nothing in any data structure can tell you so. And the partitioned-log room collects the note the first section asked you to write down. The timestamps are stamped by the producers, so without a watermark the front is only the earliest thing that has shown up. The right structure again, wrong about its input.

11The ratio, cashed

Read the fourteen aways in one breath and a single failure of the same denominator explains every one of them. The ratio has run under this course since page 4: what the answer needs to know, over what the arrangement is made to promise. The numerator belongs to your question, and the denominator belongs to the structure you reached for. Every away you just called is a mismatch between the two, and there are only three ways to mismatch.

Some rooms promised more than the answer needed. The crawler read no order at all, and the twelve backends fit in one scanned cache line. The eight ad slots and the JIT's sixteen registers sit at the same boundary, where a cache line outruns the logarithm. The wheel, the buckets and the histogram went further: somebody chose a grid for the keys, so no pairwise claim was ever owed. Some rooms promised less. The nightly file and the transparent triangles wanted the whole order, and the dedupe check wanted membership. The cancelled build wanted the middle by id, the salary study wanted one rank of a finished set, and the order log wanted both ends of a range. Each asks for something the front-only promise never bought, and the refusal is the bill, not the answer. And room #21 is the sharpest case, because the package installer's numerator was zero. The order was already in the data, so any denominator at all was overpayment.

One habit leaves this page worth more than the tool, and it travels with its hypothesis attached. In any tree whose census halves as you climb (complete, balanced, near enough), a per-node cost of that node's own height sums to linear. The census shrinks faster than the price grows, and that race is the whole theorem. Skew it into a path and the same sum pays 0 + 1 + … + (n − 1), which is quadratic. Fifteen nodes on paper settle it either way in ninety seconds, and that test is what entitles you to the move.

The build count was never about heaps. It was the first place correct reasoning charged every item the most expensive price in the building, and a countable promise caught it. That catch generalises. A heap wins by promising less, and by nothing else. So of every index, cache, tree and sorted file you meet from here, ask the same three-part question: what does this promise, how many claims is that, and does my answer need all of them?