Priority queues and selection: the next item is not the whole order

Unit six showed that a spatial index pays only while the query stays local. A priority queue promises still less: the extreme element and nothing else. A heap returns the smallest or largest key in constant time without holding a total order, so an interface that inherits its sequence from repeated extraction displays an order the structure never fixed and can reorder equal keys between runs. The repair is a total comparison, a tie-break extending the partial order the heap maintains into the total order the interface needs, and no faster heap supplies it. The literature's energy has gone into the operations rather than the order, which is why heap engineering has produced a theory-practice gap rather than a settled default.

The promise is one element, not an order

Williams (1964) introduced the binary heap and heapsort: a complete binary tree in an array, each parent outranking its children, returning the extreme element in constant time and supporting insertion and removal in logarithmic time. It keeps one invariant and does not sort. Fredman and Tarjan (1987) state the contract operationally: their Fibonacci heap deletes the extreme element in O(log n) amortised time and performs the other standard operations in O(1), with no requirement about the order of equal keys.

Selection shows how little of an order a consumer needs. Hoare (1961) published FIND: it partitions, compares the pivot's final index with the rank wanted, and recurses into one side only, giving expected linear time without sorting. The question is what happens when the displayed part must be stable though the whole order is not needed.

What the promise leaves out: equal keys are unordered

Williams's invariant is a partial order. Two equal keys each fail to outrank the other, so the heap property says nothing about their positions and both arrangements are valid: extraction fixes which key leaves the structure, and among equal keys only that some one of them does. An interface that builds its visible sequence by extracting inherits that indifference. A notification list with equal scores or a leaderboard with ties shows an order set by the heap's internal layout and its operation history, so a refresh can move tied items and read as a change that did not happen. For a person listening through a screen reader, an unannounced reorder is a list that changes under them.

The heap is doing what it promises while the interface asks for something else, and FIND is right when no order is displayed, so ties never arise. A secondary key, such as an arrival counter, extends the comparison so no two distinct items compare equal, and the extracted sequence becomes deterministic. No Fibonacci, pairing or weak heap changes this. Iacono (2000) shows the structure already depends on its history: the amortised cost of extracting x from a pairing heap is O(log min(n, k)), where k counts operations since x was inserted.

The narrow promise makes the structure reusable

Huffman (1952) built an optimal prefix code by repeatedly merging the two least frequent symbols, an algorithm whose whole mechanism is a priority queue supplying the two smallest. Johnson (1975) made decrease-key first-class and used it for minimum spanning trees, and Floyd (1964) separated build cost from running cost: his Algorithm 245 constructs a heap bottom-up by sifting down from the last internal node, in linear time rather than the n log n of inserting one at a time.

Huffman's own worked example shows the engine in full. His Table I takes thirteen messages, with probabilities from 0.20 down to 0.01, and at each step brackets the two smallest and replaces them with their sum, a message's code length being the number of times it is bracketed. The code that results averages 3.42 binary digits per message, against the four a fixed-length code needs for thirteen messages.

The bound and the constant: an unsettled choice

The literature divides into an asymptotic tradition and a measurement tradition that do not agree on what makes a priority queue good. Fredman and Tarjan (1987) gave the asymptotic high point, Fibonacci heaps with constant amortised decrease-key and merge and logarithmic deletion. Fredman, Sedgewick, Sleator and Tarjan (1986) then built a simpler self-adjusting structure, the pairing heap, intended to be competitive in theory and fast in practice, but they proved only part of what they conjectured.

Measurement cut against the theoretical ordering. Stasko and Vitter (1987) simulated pairing heaps against other implementations and found them competitive in practice, evidence for a conjecture rather than a proof. Larkin, Sen and Tarjan (2014) reimplemented classic and recent variants from scratch with only standard optimisations and measured them on artificial workloads, on algorithms over real map data and on a discrete event simulator. The implicit four-ary heap was fastest on most workloads, the Fibonacci heap almost seven times as slow as the fastest on sorting and roughly three times as slow under Dijkstra on the full United States road map, and the L1 cache miss rate tracked the wall-clock time. Their verdict is that conventional wisdom holds in some cases and is sorely mistaken in others. Iacono (2000) proved constant amortised insertion and zero amortised melding for pairing heaps, so the constant and the cache decide, not the asymptotic label.

A known distribution makes generality a cost, and a relaxed answer beats the bound

A heap assumes nothing about the keys beyond a comparison, and where the distribution is known that generality is a cost. Brown (1988) introduced the calendar queue for the simulation event set and showed it constant in queue size for the priority-increment distributions studied, with hold times three times shorter than splay trees at 10,000 events. Chazelle (2000) reaches a related conclusion from the other side: the soft heap beats the logarithmic comparison bound by artificially raising some keys, keeping at most a fraction epsilon of items corrupted and every operation constant amortised except insertion, and computes a minimum spanning tree in linear time.

Contested question: is the heap's problem the bound or the constant?

One position treats the asymptotic bound as deciding, because Fredman and Tarjan (1987) show Fibonacci heaps reach constant amortised decrease-key and merge and use that to improve graph bounds. The opposing position treats the measured cost as decisive, because Larkin, Sen and Tarjan (2014) find the implicit four-ary heap fastest on most workloads and the Fibonacci heap several times slower where it is slowest, with cache behaviour tracking the wall-clock. A third position holds the two reconcilable, the gap being incomplete analysis and unoptimised code. Iacono (2000) narrows the theoretical distance, and Edelkamp, Elmasry and Katajainen (2013) engineer the weak heap, n elements in an array plus n bits, judging its variants on cache misses and instruction counts as much as on the bound.

A study would settle the disagreement. It would report element comparisons and cache misses, not only wall-clock time, as a function of workload and key distribution with the input sequence stated, and on the operation mix the application performs, including whether decrease-key is used. Larkin and colleagues (2014) come closest and warn that certain random insertion-deletion sequences are degenerate and can mislead. No source here reports that comparison with the output order measured too, so the dispute over which heap is best has not been extended to whether the heap's indifference among equal keys is visible to the user.

Rate the positions by their evidence. Fredman and Tarjan (1987) prove the asymptotic bounds, a result about comparisons that says nothing about a cache. Larkin, Sen and Tarjan (2014) measure the heaps on real workloads and find cache misses tracking the wall-clock, the clearest measurement in the unit. The two sides met in 2024. Haeupler, Hladik, Rozhon, Tarjan and Tetek (2024) build a heap whose extraction cost is logarithmic in the number of elements inserted after the one extracted, matching the worst-case bounds of Fibonacci heaps, and prove Dijkstra with it universally optimal for ordering vertices by distance, the first application of universal optimality to a sequential algorithm. The working-set property Iacono measured in 2000 has become a design requirement certified against every graph topology rather than a constant measured once. The strongest objection is that the four-ary heap's lead is a fact about one cache, so it may not survive another machine. While the dispute is open, a designer tie-breaks every equal priority on a secondary key, because no heap in the contest fixes the order a user sees.

Where the argument is heading

The named work points two ways. One is towards structures whose value is set by the workload rather than a comparison bound: Brown's (1988) calendar queue, Johnson's (1975) radix heap and Chazelle's (2000) soft heap. The other is towards measuring the machine rather than the model. Larkin, Sen and Tarjan (2014) and Edelkamp, Elmasry and Katajainen (2013) judge structures by cache misses and instruction counts, and Iacono (2000) shows the analysis catching up to the measurements. The interface question has no equivalent body of work.

The sources this unit rests on

• Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L. and Tarjan, R. E. (1973). Time bounds for selection. Journal of Computer and System Sciences. doi:10.1016/s0022-0000(73)80033-9 Blum, Floyd, Pratt, Rivest and Tarjan show that the k-th smallest element can be selected in at most 5.4305n comparisons in the worst case, by choosing a guaranteed-good pivot. It is a worst-case theorem, the counterpart to FIND.
• Brown, R. (1988). Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem. Communications of the ACM. doi:10.1145/63039.63045 Brown introduces the calendar queue for the future event set problem and shows it constant in queue size for the priority-increment distributions studied, with hold times three times shorter than splay trees at 10,000 events. It is the case where the distribution is known.
• Chazelle, B. (2000). The soft heap: an approximate priority queue with optimal error rate. Journal of the ACM. doi:10.1145/355541.355554 Chazelle introduces the soft heap, which beats the logarithmic comparison bound by artificially raising some keys, keeping at most a fraction epsilon of items corrupted and every operation constant amortised except insertion. What a structure promises depends on what the consumer tolerates.
• Edelkamp, S., Elmasry, A. and Katajainen, J. (2013). Weak heaps engineered. Journal of Discrete Algorithms. doi:10.1016/j.jda.2013.07.002 Edelkamp, Elmasry and Katajainen study the weak heap, n elements in an array plus n bits, and catalogue algorithms that optimise construct and insert without slowing minimum or extract-min, judged on cache misses, comparisons and moves. With the bound fixed the machine decides.
• Floyd, R. W. (1964). Algorithm 245: Treesort. Communications of the ACM. doi:10.1145/355588.365103 Floyd builds a heap in linear time bottom-up by sifting down from the last internal node, replacing the n log n cost of inserting one at a time. It separates the cost of building a heap from the cost of using it.
• Fredman, M. L., Sedgewick, R., Sleator, D. D. and Tarjan, R. E. (1986). The pairing heap: A new form of self-adjusting heap. Algorithmica. doi:10.1007/bf01840439 Fredman, Sedgewick, Sleator and Tarjan introduce the pairing heap, a self-adjusting heap competitive with the Fibonacci heap in theory, easy to implement and fast in practice, with constant worst-case meld and a deletion bound proved only partly. It leaves a conjecture open.
• Fredman, M. L. and Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM. doi:10.1145/28869.28874 Fredman and Tarjan introduce Fibonacci heaps, which delete the extreme element in logarithmic amortised time and perform all other operations in constant amortised time. Its operation set is silent on the order of equal keys.
• Haeupler, B., Hladik, R., Rozhon, V., Tarjan, R. E. and Tetek, J. (2024). Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). doi:10.1109/focs61266.2024.00125 Haeupler, Hladik, Rozhon, Tarjan and Tetek give a heap whose extraction cost is logarithmic in the elements inserted after the one extracted, and prove Dijkstra with it universally optimal for distance ordering, turning a measured constant into a certified bound.
• Hoare, C. A. R. (1961). Algorithm 65: find. Communications of the ACM. doi:10.1145/366622.366647 Hoare's FIND selects the k-th smallest element by partitioning and recursing into one side only, giving expected linear time without sorting. It is the origin of selection as a problem distinct from sorting.
• Huffman, D. (1952). A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE. doi:10.1109/jrproc.1952.273898 Huffman constructs a minimum-redundancy prefix code by repeatedly merging the two least frequent symbols and proves it optimal by an exchange argument; his worked example averages 3.42 binary digits per message. The whole mechanism is a priority queue.
• Iacono, J. (2000). Improved Upper Bounds for Pairing Heaps. Lecture Notes in Computer Science. doi:10.1007/3-540-44985-x_5 Iacono proves that pairing heaps have constant amortised insertion and zero amortised melding, and shows that extract-min on an element costs O(log min(n, k)), where k counts operations since it was inserted. A heap's behaviour depends on its history.
• Johnson, D. B. (1975). Priority queues with update and finding minimum spanning trees. Information Processing Letters. doi:10.1016/0020-0190(75)90001-0 Johnson introduces priority queues supporting decrease-key and uses them to find minimum spanning trees, the radix heap giving better bounds for integer keys, and this is where the d-ary heap originates. It treats the forgotten operation as first-class.
• Larkin, D. H., Sen, S. and Tarjan, R. E. (2014). A Back-to-Basics Empirical Study of Priority Queues. Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX). doi:10.1137/1.9781611973198.7 Larkin, Sen and Tarjan reimplement classic and recent heap variants from scratch with standard optimisations only and measure them on artificial workloads, real map data and a discrete event simulator. The implicit four-ary heap is fastest on most, and cache misses track wall-clock.
• Stasko, J. T. and Vitter, J. S. (1987). Pairing heaps. Communications of the ACM. doi:10.1145/214748.214759 Stasko and Vitter simulate pairing heaps against other implementations and supply evidence for the conjecture that pairing heaps match the Fibonacci amortised bounds, while noting the structures are hard to analyse. It opens the theory-practice question experimentally.
• Williams, J. (1964). Algorithm 232: Heapsort. Communications of the ACM. doi:10.1145/512274.3734138 Williams introduces the binary heap, a complete binary tree in an array in which each parent outranks its children, and heapsort, sorting in place in n log n comparisons. The heap returns the extreme element without maintaining a full order.