GATE CSE 2014 | Set 2 | Question: 12

Question

A priority queue is implemented as a Max-Heap. Initially, it has $5$ elements. The level-order traversal of the heap is: $10, 8, 5, 3, 2$. Two new elements $1$ and $7$ are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is: 

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

Comments

what is the significance of the line in the question "A priority queue is implemented as a Max-Heap."

as the solution is just insertions into heap

---

Who says gate doesn’t repeat questions. they do…

Exactly same question word by word just they shuffled the options.

---

Proof :--   https://gateoverflow.in/1370/gate-cse-2005-question-34

---

we can say like they repeat only easy question :p

---

chandra sai

It's not exactly necessary to the question but I'd assume that the only significance is that we consider these elements given as a key value and higher key value = highest priority. So we implement it as a max heap so that whenever we need to extract the next element, the highest priority element comes out that is the element having max key value which is in root (i.e swap last element with root, delete the root(highest key value), perform heapify to maintain the heap property)

Answer 1

Answer is (A)....whenever insertion will be done in heap ,it will always inserted in last level from left to right.so we insert $1$ and $7$ as a child of node $5$ now we perform heapify algorithm until heap property will satisfied..and then we get the heap whose level order traversal is $10,8,7,3,2,1,5$.

Initial heap

After insert of $1$

After insert of $7$