80 SORTING ALGORITHMS
Final Algorithm
Putting these pieces together, and adding the final details needed to move the
elements from the heap to the list, gives the algorithm
for i = N/2 down to 1 do
FixHeap( list, i, list[ i ], N )
end for
for i = N down to 2 do
max = list[ 1 ]
FixHeap( list, 1, list[ i ], i-1 )
list[ i ] = max
end for■ 3.5.1 Worst-Case Analysis
We begin by analyzing FixHeap because the rest of the algorithm depends on
it. This algorithm will do, for each level of the heap, a comparison between the
two children and then the larger child and the key. This means that for a heap
of depth D, there will be no more than 2D comparisons.^2
In the heap construction stage, we first call FixHeap for each node on the
second level from the bottom, which means heaps of depth 1. Then it is called
for each node on the third level from the bottom, which means heaps of depth- On the last pass at the root level, the heap will have depth lgN. The only
thing we need to consider is how many nodes is FixHeap called for at each
pass. At the root level there is one node, and it has two children at the second
level. The next level down has at most four nodes, and the level after that has
eight. Putting all of this together gives the following formula:
(^2) The depth is 1 less than the level number. A heap with four levels will have a maxi-
mum depth of 3. The root is at depth 0, its children are at depth 1, their children are at
depth 2, and so on.
WConstruction()N 2 ()Di– 2 i
i=0
D–1
= ∑
WConstruction()N 2 D 2 i 2 i 2 i
i=0
D–1
- ∑
i=0
D–1
= ∑