IIIT BLR TEST 1 : ALGORITHMS 2

Question

A 3 way (ternary) min heap is a 3 way ( ternary – each node as atmost three children nodes, left, mid, right ) complete tree with min heap property ( value of the parent is less than the value of the children ) satisfied at every node. Given a ternary heap in the array representation.

(a) Write the following functions.

1. Parent(i) // returns the index of the parent of i
2. Leftchild(i)  // returns the index of the left child of i
3. Middlechild(i)  // returns the index of the Middle child of i
4. Rightchild(i)  // returns the index of the right child of i

(b) Write the pseudocode for the topdownheapify function.

(c) In Heapsort, binary heap is preferred over ternary heap. State if this statement is true or false, you must justify your answer.

Answer 1

Let the heap be represented using an array with index starting from 0. Then

left_child = 3i + 1

right_child = 3i + 2

middle_child = 3I + 3 

parent = ceil(i/3 - 1)

internal_node starts from floor(( n+1)/3  - 1)

The topdownheapify algorithm is as follows

 

min_heapify(A,i)
{
    child_min = min(x,y,z) // x,y,z are the left,middle and the right child respectively of A[i].
    k = index(child_min)   // child_min is mininum of the children
    if (root > child_min)
        exchange(A[k],A[i])
        min_heapify(A,k)
}

build_heap(A)
{
    for( i = 0 to floor((n+1)/3 - 1))
        min_heapify(A,i)
}