CSC 378: Data Structures and Algorithm Analysis

Buildheap, with Analysis

[CLR 7.3]

Building a Heap

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

Look at it as a tree:

In the example, index1.gif , so index2.gif 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! index3.gif

Analysis of BuildHeap

The easy way: Each Heapify takes index4.gif time, and there are index5.gif calls to Heapify, so

index6.gif

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:

index7.gif

The number of nodes at height i is at most index8.gif .

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

So the cost of BuildHeap is

index10.gif

Therefore, index11.gif

Heapsort

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 index12.gif time and each of the index13.gif ExtractMaxs takes index14.gif time, the array is sorted in index15.gif time.




Back to the lecture index

Copyright 1998 James Stewart