CS 502 Fundamental of Algorithms Assignment # 02 Solution Fall 2012

CS 502 Fundamental of Algorithms

Assignment # 02

Fall 2012

Total Marks = 20

CS 502 Fundamental of Algorithms

Assignment # 02

Fall 2012

Total Marks = 20

Read more: CS502 - Fundamentals of Algorithms Assignment # 2 discussion and solution Due date is November 27, 2012. - Virtual University of Pakistan http://vustudents.ning.com/group/cs502fundamentalsofalgorithms/forum/topics/cs502-fundamentals-of-algorithms-assignment-2-discussion-and#ixzz2DOpOfZ5B

 SOLUTION:

Outline of Procedure Heapify

Heapify picks the largest child key and compare it to the parent key. If parent key is larger than heapify quits, otherwise it swaps the parent key with the largest child key. So that the parent is now becomes larger than its children.
It is important to note that swap may destroy the heap property of the subtree rooted at the largest child node. If this is the case, Heapify calls itself again using largest child node as the new root.

Heapify (A, i)

1.     l ← left [i]

2.     r ← right [i]

3.     if l ≤ heap-size [A] and A[l] > A[i]

4.         then largest ← l

5.         else largest ← i

6.     if r ≤ heap-size [A] and A[i] > A[largest]

7.         then largest ← r

8.     if largest  ≠ i

9.         then exchange A[i] ↔ A[largest]

10.         Heapify (A, largest)

 

Analysis

If we put a value at root that is less than every value in the left and right subtree, then 'Heapify' will be called recursively until leaf is reached. To make recursive calls traverse the longest path to a leaf, choose value that make 'Heapify' always recurse on the left child. It follows the left branch when left child is greater than or equal to the right child, so putting 0 at the root and 1 at all other nodes, for example, will accomplished this task. With such values 'Heapify' will called h times, where h is the heap height so its running time will beθ(h) (since each call does (1) work), which is (lgn). Since we have a case in which Heapify's running time (lg n), its worst-case running time is Ω(lgn).

 

Example of Heapify
 

Suppose we have a complete binary tree somewhere whose subtrees are heaps. In the following complete binary tree, the subtrees of 6 are heaps:

The Heapify procedure alters the heap so that the tree rooted at 6's position is a heap. Here's how it works. First, we look at the root of our tree and its two children.

We then determine which of the three nodes is the greatest. If it is the root, we are done, because we have a heap. If not, we exchange the appropriate child with the root, and continue recursively down the tree. In this case, we exchange 6 and 8, and continue.

Now, 7 is greater than 6, so we exchange them.

We are at the bottom of the tree, and can't continue, so we terminate.