GATE CS 2014 Set 2 Q.22 (CS Q.12): Binary Heaps and Priority Queues

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:

10, 8, 7, 3, 2, 1, 5

10, 8, 7, 2, 3, 1, 5

10, 8, 7, 1, 2, 3, 5

10, 8, 7, 5, 3, 2, 1

Official answer and solution

Official answer: A
From: Official GATE 2014 answer key

Solution

Simulate successive heap insertions into the Max-Heap and read out the resulting array level by level.

Initial Max-Heap Array Representation (1-indexed):
- Indices: 1: 10, 2: 8, 3: 5, 4: 3, 5: 2
- Level-order traversal: 10, 8, 5, 3, 2.
Insert Element 1:
- Place $1$ at the next available position: index $6$ (left child of index $3$ , which is $5$ ).
- Compare with parent at index $3$ ( $5$ ): since $1 < 5$ , max-heap property is satisfied.
- Heap array: [10, 8, 5, 3, 2, 1].
Insert Element 7:
- Place $7$ at the next available position: index $7$ (right child of index $3$ , which is $5$ ).
- Compare with parent at index $3$ $3$ ( $5$ $5$ ): since $7 > 5$ $7 > 5$ , swap $7$ $7$ and $5$ $5$ .
  - Index $3$ becomes $7$ .
  - Index $7$ becomes $5$ .
- Compare new element at index $3$ $3$ ( $7$ $7$ ) with its parent at index $1$ $1$ ( $10$ $10$ ):
  - Since $7 < 10$ , no further swap is needed.
- Heap array: [10, 8, 7, 3, 2, 1, 5].
The level-order traversal of the final heap is 10, 8, 7, 3, 2, 1, 5 (option A).

Final answer

Common trap

Swapping 7 all the way to the root without checking against parent 10.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 2
Question: 22 of 65, printed as CS Q.12
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source