With A[1...n] initially randomly filled, execute:

Look at it as a tree:

In the example, , so and the code executes:

heapify(A,6)
heapify(A,5)
heapify(A,4)
heapify(A,3)
heapify(A,2)
heapify(A,1)

Ordering is important!

The easy way: Each Heapify takes time, and there are calls to Heapify, so

But a more detailed analysis yields a tighter bound. Heapify(i) takes time proportional to the height of node i. So count the individual steps:

The number of nodes at height i is at most .

The cost of Heapify at height i is at most per node.

So the cost of BuildHeap is

Therefore,

Here's the Heapsort procedure, which reorganizes the array so that A[1], A[2], ... A[n] are in increasing order:

HeapSort(A,n) BuildHeap(A,n) for i=0 to n-1 A[n-i] = ExtractMax(A)

Since BuildHeap takes time and each of the ExtractMaxs takes time, the array is sorted in time.