Chapter 6 - Heapsort
Document last modified: 

Heapsort

  1. Constructs an array satisfying the max-heap property.
     
  2. Sorts the array in ascending order.
Build_Max_Heap (A)
1 A.heap-size ← A.length
2 for i ← ⌊A.length/2⌋ downto 1 do
3    Max_Heapify (A, i)

 
Heapsort (A)
//@ pre A != null;
//@ modifies A[*];
//@ post (\forall int i;
                    1 <= i && i <= A.length-1;
                    A[i] <= A[i+1]);
1 Build_Max_Heap (A)
2 for i ← A.length downto 2 do
3       exchange A[1] ↔ A[i]
4       A.heap-size ← A.heap-size - 1
5       Max_Heapify (A, 1)

Prior to Heapsort

Question 6.7 - For tree (b), what is A after Line 4? After Line 5?

During Heapsort

Running time of Heapsort

Build_Max_Heap (A)
1 A.heap-size ← A.length
2 for i ← ⌊A.length/2⌋ downto 1 do
3    Max_Heapify (A, i)
Heapsort (A)
1 Build_Max_Heap (A) O(n)
2    for i ← A.length downto 2 do n*O(1)
3       exchange A[1] ↔ A[i] (n-1)*O(1)
4       A.heap-size ← A.heap-size[A] (n-1)*O(1)
5       Max_Heapify (A, 1) (n-1)*Θ(lg n)

Analysis of Heapsort

Question 6.7 - Remember our initial mistake on thinking Build_Max_Heap was O(n lg n) by assuming a tree of height lg n for each of the n applications of Max_Heapify - are we making the same mistake again?

Consider the running time of each line in the Heapsort algorithm.

Recall that Build_Max_Heap (section 6.3)

T(n)Build_Max_Heap = O(n)

1. Build_Max_Heap must visit at least  ⌊n/2⌋  nodes, running Max_Heapify at each node. O(n).

2. O(1), repeated n times, so O(n).

3. O(1), repeated n − 1 times, so O(n).

4. O(1), repeated n − 1 times, so O(n).

5. Running time equal to the running time of Max_Heapify, repeated n−1 times.

Recall that we have already derived that for Max_Heapify (section 6.2 of the text)

T(n)Max_Heapify = Θ(lg n)

Since the running time of Max_Heapify is Θ(lg n), the overall running time for Heapsort is:

T(n)Heapsort = T(n)Build_Max_Heap + (n-1)T(n)Max_Heapify
  = O(n) + (n-1) Θ(lg n) 
  = O(n) + Θ(n lg n)
  = Θ(n lg n)