Sifting down from the last internal node to the root turns any array into a heap, and it costs Σ ⌈n/2ʰ⁺¹⌉·h, which is under 2n — not n log n. The reason is that height is not shared out equally: half the nodes are leaves and sift no distance at all. At n = 31 the sum is 26 against 2n = 62, and inserting the same keys one at a time swaps 98 times.
Core ideas
One counting idea, and it is the reason a whole family of bounds is smaller than it looks: when a cost varies across the things you are summing over, multiplying the worst cost by the count throws the answer away.
In a complete tree on n nodes, about n/2 are leaves with height 0, about n/4 have height 1, about n/8 have height 2. The number of nodes at height h is at most ⌈n/2ʰ⁺¹⌉, and it halves as the cost doubles. That is the entire reason the total is linear, and it is a fact about the shape of the tree rather than about heaps.
n nodes and log n levels invites n log n, and the step that is wrong is charging every node the height of the tree. Only one node has that height. Multiplying the maximum by the count is an upper bound and it is off by a factor of log n here, which is the difference between an algorithm that is worth having and one that is not.
Sifting DOWN from the bottom up is correct because when node i is processed, both of its subtrees are already heaps, so one sift fixes it. Sifting UP from the top down would be the insertion method in disguise and would cost the same as it. The saving is not a trick of implementation; it is a different order of operations.
The material
Why sifting down from the middle is correct, the exact evaluation of the sum at n = 31, and what the two methods actually measure.
Every position past ⌊n/2⌋ is a leaf, and a leaf is a one-element heap already. So a heap can be built by sifting down at every position from ⌊n/2⌋ back to 1, in that order. The order is what makes it correct: when the pass reaches node i, everything below i has already been processed, so both subtrees of i are heaps and a single sift-down from i puts i where it belongs.
Given an array of n keys in any order, for i from ⌊n/2⌋ down to 1, sift down at position i. The result is a heap, and the cost is the total distance sifted.
The loop touches only the internal nodes, since leaves have nothing to sift past. The bound is about the total distance, so it needs the number of nodes at each height and not merely the height of the tree.
A node at height h sifts at most h levels, and a complete tree on n nodes has at most ⌈n/2ʰ⁺¹⌉ nodes at height h. So the total distance sifted is at most Σ ⌈n/2ʰ⁺¹⌉·h, summed over h = 0 to ⌊log₂ n⌋.
Dropping the ceilings, that is at most n · Σ h/2ʰ⁺¹, and Σ h/2ʰ over all h ≥ 0 converges to 2. So the sum is under 2n, and the build is Θ(n): linear in the number of keys, with no logarithm anywhere in it.
The Σ h/2ʰ = 2 step is the only piece of analysis being imported, and it is the standard arithmetico-geometric sum — differentiate the geometric series, or notice that the sum S satisfies S = S/2 + 1. Discrete Mathematics’ “Recursion Trees and Amortised Analysis” is where sums of this shape are collected; nothing else here needs it.
The lab evaluates the sum term by term rather than quoting the 2n bound, because the terms are where the insight is. At n = 31 the complete tree has five levels and the nodes are distributed like this:
Sixteen of the thirty-one nodes contribute nothing at all, and the two heights that contribute most are 1 and 2 — not the height of the tree. The total is 26, which is 26/31 of a swap per element. Compare that with what n log₂ n would have suggested: 31 × 4 is 124, nearly five times as much, and the error is entirely in charging every node the root’s height.
Now the measurement. Feed both methods the keys 31, 30, …, 1 — decreasing order, which is the worst case for insertion because every arriving key is smaller than everything present and sifts to the root:
Floyd’s swap count is 26, which is the sum exactly: this input makes every internal node sift its full height, so the bound is attained rather than merely respected. Insertion swaps 98 times on the same keys, a factor of 3.8. And on keys already in increasing order both methods swap zero times and make the same thirty comparisons, producing the same heap — a measurement taken there would show no difference between a linear algorithm and a linearithmic one.
Two things in that table are worth being careful about. First, the exact sum bounds the swaps, not the comparisons: Floyd’s comparisons are 52, about twice its swaps, because each level of a sift-down compares the two children before comparing with the parent. The 2n bound is a bound on distance sifted. Second, on a shuffled input Floyd swaps 21 — below the sum, because a random arrangement does not make every node sift its full height. The sum is the worst case; the counter shows one case.
Interactive
The sum of heights, evaluated rather than asserted
Method
The sum before the code. Evaluating it once at a small n is what makes the linear bound believable rather than memorised.
⌈n/2ʰ⁺¹⌉ for h = 0, 1, 2, … up to ⌊log₂ n⌋. Write the column out. The fact that it halves while the cost doubles is the whole argument, and it is invisible if you only write down the height of the tree.
h times the node count, summed. Keep it as an integer; there is no rounding anywhere in this sum. Then compare it with 2n, and with n⌊log₂ n⌋ to see what the loose bound would have cost you.
Sifting down, not up, and starting at the last internal node. Going the other way is the insertion method: it still produces a heap and it costs the insertion method’s price, which is the point of the comparison.
Decreasing order is the worst case for insertion and makes Floyd’s swap count hit the sum. Increasing order makes both methods do nothing. A measurement on already-sorted input cannot distinguish the two algorithms at all, and that is the trap this lab is arranged to expose.
A smaller tree, where the whole sum fits on four lines and the two measured counts can be checked against it.
Floyd’s 11 swaps equal the sum 11 exactly on the decreasing input, and its 22 comparisons are twice that, one pair per level sifted. The insertion method pays 34 on the same keys: three times as much, at a size where n⌊log₂ n⌋ is 45 and 2n is 30.
The increasing-order rows are the honest half of the exercise. Both methods swap nothing and compare fourteen times, and they produce the same heap, because the array was already one. Anyone who measured there and concluded the two builds are equivalent would have a perfectly reproducible result and a false belief, which is what this course means by a count not being a bound.
For a faded rehearsal, do n = 7. The supplied first line is that the node counts are 4, 2, 1 at heights 0, 1, 2. Finish the sum, predict Floyd’s swap count on decreasing input, and then check it in the lab — it is 4, against 10 for seven insertions and 2n = 14. Then state what the sum is a bound on, in the lab’s own columns, and what it is not.
You should be able to write the node-count column for a stated n, evaluate the sum exactly as an integer, say which measured column it bounds and which it does not, and name an input order on which the two build methods are indistinguishable and explain why that is not evidence about either.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.