Building a heap from the bottom

Turning an array into a heap has two standard methods and one standard comparison between them.

Repeated insertion. Take the elements one at a time and sift each up into the heap built so far. Each insertion costs at most the height, so the total is $O(n \log n)$.

Bottom-up, or Floyd’s method. Start at the middle of the array and sift each element down, working backwards to the front. Each sift costs at most the height of its subtree, and most subtrees are tiny — half the nodes are leaves and cost nothing, a quarter are one level up and cost one — so the total telescopes to $O(n)$.

The comparison is presented as linear against linearithmic, and the natural conclusion is that repeated insertion is a logarithmic factor worse. At $n = 65{,}536$ that factor would be sixteen.

Measured on random input, it is 1.21.

The measurement #

Comparisons, on random input from a stated seed:

Bottom-up construction divided by $n$ is 1.813, 1.855, 1.876, 1.877, 1.883, 1.881 — flat to within 4% across a 512-fold range, at 1.87 comparisons per element. The linear class fits at a spread of 1.04.

Repeated insertion divided by $n$ is 2.09, 2.13, 2.26, 2.26, 2.28, 2.28. The linear class fits it at a spread of 1.09, and the linearithmic class fits at 2.10 and is refused.

Repeated insertion is linear on random input, measured across three orders of magnitude, and it is 21% more expensive than the method that is famous for being linear.

Why the worst case does not show up #

The sift-up in an insertion walks from a leaf towards the root, stopping as soon as the parent is larger. The $\log n$ in the bound is what happens when it never stops early — when the new element is larger than everything already in the heap and travels the whole way.

On random input, the new element is the largest so far with probability $1/i$ at step $i$, so it usually stops after a step or two. Summing the expected travel over all insertions gives a constant per element, and the constant is a small one. The worst case requires every element to be a new maximum, which means the input arrives in ascending order.

So the two methods are not linear-against-linearithmic. They are:

• bottom-up: $\Theta(n)$ always, on every input;
• repeated insertion: $\Theta(n)$ on random input, $\Theta(n\log n)$ on ascending input.

Which is the same shape as insertion sort, and it is the shape that a single headline class always hides. One of those algorithms has a class and the other has a class per input, and the summary reports the worst entry of the second as though it were the first kind of statement.

The input where the factor is real #

On ascending input at $n = 16{,}384$:

A factor of exactly 6.0 in comparisons and 12.0 in swaps. The insertion count is $12n$, and $\log_2 16{,}384 = 14$ — every element travels almost the full height, because every element is a new maximum.

And on descending input both methods spend 16,383 comparisons and zero swaps, because a descending array already satisfies the max-heap property and both methods spend their time confirming it.

Three inputs, and the ratio between the two methods is 6.0, 1.21 and 1.00. There is no single number that describes how much worse repeated insertion is.

Why bottom-up is linear, in one paragraph #

The telescoping argument is worth having in full, because it is short and because the intuition that “most of the work is at the top” gets it backwards — which is the same mistake the merge-sort excess makes.

A heap of $n$ nodes has about $n/2$ leaves at height 0, $n/4$ at height 1, $n/8$ at height 2, and so on. Sifting a node of height $h$ costs at most $h$ swaps and $2h$ comparisons. So the total is bounded by

$$\sum_{h \ge 0} \frac{n}{2^{h+1}} \cdot h \;=\; n \sum_{h\ge 0} \frac{h}{2^{h+1}} \;=\; n$$

because $\sum h/2^{h+1}$ converges to 1. The expensive nodes are rare in exactly the proportion needed to keep the sum finite: there is one node of height $\log n$ and it costs $\log n$, which is a vanishing share of a linear total.

Measured, the swap count is 1.87 comparisons and 0.74 swaps per element at $n = 65{,}536$ — against the bound’s 2 comparisons per element. The bound is tight to within 7%, which is unusual for a bound derived by a series of upper estimates.

What the choice actually costs #

Given a factor of 1.21 on random input, the practical case for bottom-up construction is weaker than the classes suggest and it is not zero, and it is worth separating the three reasons.

The worst case is real and is a common input. Ascending order is not a contrived adversarial arrangement; it is the shape of any sequence that arrives sorted, which is most of them. Bottom-up construction is 6 times cheaper there and identical on random input to within 21%, so it is never worse and sometimes much better.

Only one of them can be done at all in some situations. Bottom-up construction needs every element in hand before it starts. A priority queue that receives elements over time has no choice but repeated insertion, and the comparison does not arise. This is why heapsort uses the bottom-up method — the array is right there — and why Dijkstra’s queue uses insertions.

The measured gap is not stable either. The ratio runs 1.155, 1.145, 1.207, 1.206, 1.211, 1.211 across the sweep — rising for the first few doublings and then settling. A constant that has only just stopped moving at $n = 32{,}768$ is a constant quoted at the reader’s risk, and it is the drift the constants field is about in miniature: the number is real, it is reproducible, and it is a number for a range rather than for the algorithm.

Their swap counts differ more than their comparison counts. On random input at $n = 65{,}536$, bottom-up does 48,702 swaps and insertion does 83,748 — a factor of 1.72 against the comparison factor of 1.21. Data movement is the count that usually decides when the elements are anything larger than an integer, and it is the count that most favours the bottom-up method.

None of those is “it is a logarithmic factor faster”, which is the reason usually given.

Where heapsort’s cost actually is #

Heapsort is construction followed by extraction: build the heap, then repeatedly swap the root to the end and sift the new root down over a shrinking heap. The construction is the linear phase this essay is about. Splitting one run into its two phases:

Construction is under a tenth of the algorithm and its share is falling — linear against linearithmic, exactly as the classes predict, which is one of the rare places on this site where the classes describe the behaviour without a caveat.

Three consequences follow, and the first is the practical one.

Optimising the linear phase is optimising 6.5% of the algorithm. The difference between the two construction methods on random input is 21% of a phase that is 6.5% of the total, which is 1.4% of heapsort. The choice between them is worth making because bottom-up is not harder to write, and it is not worth thinking about for more than a minute.

The extraction phase is where the interesting inefficiency is. Each extraction sifts an element taken from the bottom of the heap all the way down again, and that element is almost always small, so the sift almost always travels the full height. The measured extract ÷ $n\log_2 n$ constant is 1.69 at $n = 65{,}536$ against merge sort’s 0.838 — heapsort compares about twice as much as merge sort, and essentially all of the excess is here.

There is a well-known variant that addresses exactly this. Bottom-up heapsort — Wegener’s, confusingly named, and unrelated to Floyd’s construction — observes that the sifted element usually ends near the bottom, so it walks the path of larger children to the leaf first, then searches back upwards for the insertion point. That takes the comparisons per extraction from about $2\log n$ to about $\log n$, and it is the change that would matter. This site does not implement it, so no number for it is quoted here.

The two phases have opposite locality. Construction sifts small subtrees, which are contiguous stretches of the array; extraction sifts from the root through the whole array. Heapsort’s poor access pattern is an extraction-phase property, and the linear phase this essay is about is the well-behaved part in both resources at once.

What an average-case bound would have said #

The gap between $\Theta(n \log n)$ and the measured $2.22n$ is not a failure of the analysis. It is the difference between a worst-case bound and an average-case one, and the average-case one is derivable in three lines — which makes its absence from every account of this algorithm the interesting part.

Insert element $i$ into a heap of $i-1$ elements. It travels to the root only if it is the largest of the $i$, which for a random arrival order happens with probability $1/i$. It travels at least $k$ levels only if it beats the $2^k - 1$ elements on the path above it, which happens with probability about $2^{-k}$. So the expected travel is

$$\sum_{k \ge 1} 2^{-k} = 1$$

levels, independent of $i$ and independent of $n$. Summed over $n$ insertions: a constant per element, and the constant is small.

That derivation is not hard, it is not new, and it produces a better answer than the one everybody quotes — an exact class rather than an upper bound that overstates by a factor of sixteen. The measured 2.22 comparisons per element is two comparisons per level travelled plus the one that stops the walk, which is what the derivation predicts.

Two questions follow and only one of them has a satisfying answer.

Why is the worst case the one taught? Because it is the one that composes. A bound that holds on every input can be used inside another analysis without checking anything; an average-case bound carries a distributional assumption that has to be discharged every time it is used. That is a real reason and it is why worst-case analysis is the default in the field.

Why is the average case not taught beside it? No good reason. It is three lines, it is exact, it explains the behaviour anybody who measures will observe, and its absence leaves the impression that a structure is a logarithmic factor worse than it is. This is the same complaint the constants field makes: the missing number is not hard to obtain, and the habit of not obtaining it is the whole of the problem.

Both readings hold at other ranges, which is the check that the two lines are classes rather than coincidences of where the sweep stopped.

Which method a priority queue can use #

There is one setting where the comparison in this essay does not arise, and it is the commonest use of a heap.

A priority queue receives its elements over time. There is no array to sift down over, so bottom-up construction is unavailable and repeated insertion is the only option. Dijkstra’s algorithm pushes $V$ times, pops $V$ times and decrease-keys somewhere between zero and $E$ times, and none of those is a heapify.

Which means the linear-time construction, elegant as it is, applies to exactly one situation: an array that is already in hand and is about to be consumed as a heap. That is heapsort, and it is heapsort’s first phase, and — as the phase split above shows — it is 6.5% of heapsort at $n = 65{,}536$.

The result is real, the derivation is beautiful, and its applicability is narrower than its fame. Worth saying, because a linear-time algorithm for something that sounds like it should cost $n\log n$ is exactly the kind of result that gets remembered without its scope.

Why one walk stops early and the other does not #

Two of this essay’s constants look unrelated and have one cause, and stating it explains both at once.

A sift-up stops almost immediately. The derivation above gives an expected travel of one level, because the inserted element has to beat everything on the path to the root and the chance of beating $2^k-1$ elements falls like $2^{-k}$.

A sift-down travels almost the whole way. Bottom-up construction measures 1.87 comparisons per element against a bound of 2 — tight to 7% — which means the descents are going nearly as far as the bound allows.

Both follow from the same fact about a heap’s shape: most of the nodes are near the bottom. A subtree of height $h$ has half its nodes in the bottom level and three quarters in the bottom two. So an element being sifted down into a random subtree is being placed among nodes that are mostly deep, and it usually belongs deep — while an element being sifted up is being compared against nodes that are mostly shallow relative to it, and it usually loses immediately.

That is one asymmetry producing two constants in opposite directions, and it is why the bound is loose in one case and tight in the other. Repeated insertion’s $O(n\log n)$ overstates by a factor of sixteen because the walk almost never goes far; bottom-up’s $2n$ overstates by 7% because the walk almost always does.

It also settles which of the two bounds is worth quoting. A bound whose slack is 7% is a description; a bound whose slack is a factor of sixteen is a permission. The two are written in the same notation and the difference between them is not visible in it — which is the constants field’s standing complaint, arriving here as a statement about bounds rather than about classes.

The branching factor, and which phase chooses it #

The phase split above says construction is 6.5% of heapsort and extraction is the rest, and there is a parameter that trades between them which the essay has held fixed at two.

A $d$-ary heap gives each node $d$ children instead of two. Its height is $\log_d n$, so:

A sift-down costs more per level and there are fewer levels. Each level compares $d$ children to find the largest and then one more against the element, so the cost is about $d\log_d n = d\log_2 n / \log_2 d$ — which is minimised at $d = 2$ and rises from there. Extraction, which is all sift-downs, wants a binary heap.

A sift-up costs one comparison per level and there are fewer levels. So its cost is $\log_d n$, which falls as $d$ grows. Insertion and decrease-key want a wide heap.

And construction stays linear at every $d$, by the same telescoping argument with a different ratio.

So the parameter is decided by which operation dominates. Heapsort is extraction-dominated and takes $d = 2$. Dijkstra’s algorithm performs up to $E$ decrease-keys against $V$ pops, so on a sparse graph the sift-ups outnumber the sift-downs and a four-ary heap is the common recommendation — a small improvement to the term that dominates, bought at almost no cost, which is exactly why it survives where the asymptotically better structures do not.

The same structure, two workloads, two different right answers for a number that appears in no complexity class. That is this collection’s most repeated finding and it is worth noting that it arrives here as a consequence of the phase split rather than as a separate observation: knowing which phase dominates is what makes the parameter decidable at all.

The general form #

This essay is the third case on the site of a declared class being refused by measurement, and it is the mildest and the most typical of the three.

Bubble sort on nearly sorted input fits neither of its candidate classes. The hybrid on reversed input fits different classes over different ranges. Here, repeated insertion fits $n$ on the input everybody uses and $n\log n$ on the input the bound is about, and both fits are clean.

What all three have in common is that the published class is correct and describes a case. What differs is how far the case is from the common one, and this is the one where the distance is largest: a factor of sixteen predicted, a factor of 1.21 observed.

The reason to keep saying this is that the failure is systematic rather than occasional. A worst-case bound is the maximum over a set, the maximum is attained somewhere, and where it is attained is a fact about the input that the notation is designed to discard. Every time this site measures a worst-case bound against a typical input, the two are different, and the size of the difference is not predictable from the bound.