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.

  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.

in Algorithms by | 163 views

1 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


    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)

    for( i = 0 to floor((n+1)/3 - 1))



Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,314 questions
60,435 answers
95,251 users