GATE CSE 2006 | Question: 77

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$

77. Suppose the elements $7, 2, 10$ and $4$ are inserted, in that order, into the valid $3$-ary max heap found in the previous question, Q.76. Which one of the following is the sequence of items in the array representing the resultant heap?

• A. $10, 7, 9, 8, 3, 1, 5, 2, 6, 4$
• B. $10, 9, 8, 7, 6, 5, 4, 3, 2, 1$
• C. $10, 9, 4, 5, 7, 6, 8, 2, 1, 3$
• D. $10, 8, 6, 9, 7, 2, 3, 4, 1, 5$

Comments

sir 76th question is not complete ??

---

yes, that is separated as a new question for making the Exam. You can see the link below in related questions.

---

For 76 answer is D.

For 77 answer is A.

Answer 1

Heap will be constructed like this, based on the correct answer of Q.76 $($which is $\quad9\quad5\quad 6 \quad8\quad 3\quad 1)$

Correct Answer: $A$

Comments

The question describes insertion operation as:

"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."

We are supposed to heapify separately for each new element we put into the array, thus total $4$ times here.

---

yes for this question we have to do heapification after each insertion of node

And if nothing mentioned in question then also we do it in same way.

means we generally do (insertion 1 element) →(heapify) →(insertion another element) →(heapify).......... right?

---

Yes.

Answer 2

heap will be like this in the start               @                               suppose = @ is a node with no value filled. We know exactly

                                                 @               @             @                 how heapify going to work . for example 7 will be move

                                       @    @    7      2    10     4                           upward from it's current  leaf  position to root node path.

                                                                                                                if you  draw each and every heap from the options.                                                                                                                       you can  see  there is only 'A' option, which has 7 on its 2nd level right position that is it's parent position. so, option 'A'.

Note ; as for 10 it will move to root node with it's own path