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)

}

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,492 answers

195,439 comments

100,700 users