The Gateway to Computer Science Excellence
0 votes
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.

in Algorithms by Veteran (64.7k points) | 99 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

 

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)

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
50,647 questions
56,492 answers
195,439 comments
100,700 users