99 views

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.

| 99 views

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)
}

by (17 points)