GATE CSE 2006 | Question: 76

Question

Statement for Linked Answer Questions 76 & 77:

A $3$-ary max heap is like a binary max heap, but instead of $2$ children, nodes have $3$ children. A $3$-ary heap can be represented by an array as follows: The root is stored in the first location, $a[0]$, nodes in the next level, from left to right, is stored from $a[1]$ to $a[3]$. The nodes from the second level of the tree from left to right are stored from $a[4]$ location onward. An item $x$ can be inserted into a $3$-ary heap containing $n$ items by placing $x$ in the location $a[n]$ and pushing it up the tree to satisfy the heap property.

76. Which one of the following is a valid sequence of elements in an array representing $3$-ary max heap?

• A. $1, 3, 5, 6, 8, 9$
• B. $9, 6, 3, 1, 8, 5$
• C. $9, 3, 6, 8, 5, 1$
• D. $9, 5, 6, 8, 3, 1$
   

Comments

Not able to believe this from 2006 cse paper till now all 2006 question are nightmare from all the subject

Answer 1

D.
The method to solve is clearly given in the question itself. Just one thing to mention is the heap property. Max Heap = The parent is always greater or equal to the child. if not then swap the respective child with the parent to satisfy the property of the heap.

Answer 2

Heap has important property if it max heap then parent always greater than or equal to its two child... dont matter lest or right child in any oder..

and one important property if left child present then only right present ... i.e. it is not the case right child present but left child not present...

 if it min heap then parent always less than or equal to its two child..

Heap stored in array as

Parent then left child then right child.. then left child as root then its left chils then right child.....

if any place some thing mis then vacant thats place in array..