The GATE Grind

GATE 2015 CS – Question 37

Programming and Data Structures · Binary Heaps · 2 marks · Multiple choice

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.

Array Index123456789
Value4030201015161784

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

  1. 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
  2. 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
  3. 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
  4. 40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) 40, 35, 20, 10, 30, 16, 17, 8, 4, 15

Explanation

35 is placed at index 10, whose parent at index 5 holds 15. Since 35 is larger, they swap, so 35 moves to index 5 and 15 to index 10. The new parent at index 2 holds 30, which is smaller than 35, so they swap again and 35 reaches index 2. Its parent 40 is larger, so it stops. The heap is 40, 35, 20, 10, 30, 16, 17, 8, 4, 15.