The Gateway to Computer Science Excellence

0 votes

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.

- Parent(i) // returns the index of the parent of i
- Leftchild(i) // returns the index of the left child of i
- Middlechild(i) // returns the index of the Middle child of i
- 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.

0 votes

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)

}

52,314 questions

60,435 answers

201,773 comments

95,251 users