Heap Sort

A[1 ... n], n = length[A] = heap-size[A]

After Build-Heap; A[1] is the max. Exchange A[1] « A[n], and  decrement heap-size. A[1 ... (n-1)} is almost a heap, it requires at most one Heapify ( A, 1 ).

The cost of Heapsort is O ( n lg n ) as Build-heap is called once, and Heapify is called at most n times.

Heapsort (A)

1. Build-Heap (A)

2. for i ¬ length[A] downto 2

3.        do exchange A[1] « A[i]

4.        heap-size[A] ¬ heap-size[A] - 1

5.        Heapify ( A, 1 )