Wednesday, June 18, 2008


Build-Heap (H)

The above Procedure builds up the heap in a bottom up manner by using Heapify. All array elements in a subarrray are all leaves of the tree. Thus, each leaf is a heap of size 1.
Step 1 Initialization
set heap-size [H]  length [H]
Step 2 fixing
for i  down to 1
call to Heapify (H, i)
Procedure Heap-sort (H)
The above procedure sorts the element of a given array using heap sort technique. The procedure makes a call to Build-Heap, and Heapify.
Step 1 Building
Call to Build-heap (H)
Step 2 loop, exchanging root, and fixing the heap.
for i  length [H] down to 2
set H [1]  H [i]
set heap-size [H] ¬ heap-size [H] – 1
call to Heapify (H, 1)
Step 3 return at the point of call

No comments: