retagged by
732 views
0 votes
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.

retagged by

1 Answer

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

 

Related questions

1 votes
1 votes
1 answer
1
Shaik Masthan asked Aug 27, 2019
1,017 views
Given an array of ( both positive and negative ) integers, $a_0,a_1,….a_{n-1}$ and $l, 1<l<n$.Design a linear time algorithm to compute the maximum product subarray, wh...
0 votes
0 votes
1 answer
3
0 votes
0 votes
1 answer
4
Shyam Singh 1 asked May 17, 2016
822 views
$6.2-3$What is the effect of calling MAX-HEAPIFY(A,i) when the element A[i] is larger that its children?