CSC 378: Data Structures and Algorithm Analysis
Buildheap, with Analysis
[CLR 7.3]
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.