Analysis of Algorithms : An Active Learning Approach

3.5 HEAPSORT 81

Using Equations 1.17 and 1.19, we get

We now substitute D = lg N, giving

So the heap construction phase is linear with respect to the number of ele-
ments in the list.
Now we consider the main loop of the algorithm. In this loop, we remove
one element from the heap and then call FixHeap. This gets repeated until
there is only one element left in the heap. On each pass the number of ele-
ments decreases by 1, but how does this change the depth of the heap? We have
already said that the entire heap has a depth of lgN, and so it is easy to see
that if there are K nodes left in the heap, it will have depth of lgK, and the
number of comparisons is twice this number. This means that the worst case
for the loop is

The problem we now have is that there is no standard form for this summation.
Let’s think about how this breaks down. When k is 1, lgk will be 0. When k is
2 and 3, lgk will be 1. When k is 4 through 7, lgk will be 2. When k is 8
through 15, lgk will be 3. We notice that in each of these cases, when the
result is j, there are 2j values that give that result. This will be true for all but the
last level of the heap if it is not complete. On that level, we see that there are N

2 lgN elements.^3 This means that our equation can be represented as:

(^3) Because there is a floor involved with the exponent of 2, 2lgN < N, except when N
is an exact power of 2, and then these are equal.
WConstruction()N = 2 D() 2 D– 1 – 2 []()D– 22 D+ 2
WConstruction()N = 2 D+1D– 2 D– 2 D+1D+ 2 D+2– 4
WConstruction()N = 2 D+2– 2 D– 4
WConstruction()N = (^42) * lgN–2 lg N– 4
WConstruction()N == 4 N–2 lg N– 4 ON()
Wloop()N 2lgk
k=1
N–1
∑ 2lgk
k=1
N–1
==∑
Wloop()N 2 k 2 k
k=1
d–1
∑

==+dN()– 2 d whered lgN