The GATE Grind

GATE 2016 CS – Question 47

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

An operator `delete(i)` for a binary heap data structure is to be designed to delete the item in the $i$-th node. Assume that the heap is implemented in an array and $i$ refers to the $i$-th index of the array. If the heap tree has depth $d$ (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?

  1. $O(1)$
  2. $O(d)$ but not $O(1)$
  3. $O(2^d)$ but not $O(d)$
  4. $O(d \, 2^d)$ but not $O(2^d)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $O(d)$ but not $O(1)$

Explanation

To delete the item at index $i$, move the last element of the heap into that position. Then it may need to move up or down along one root-to-leaf path to restore the heap property, which takes at most $d$ swaps. That is $O(d)$, and it is not $O(1)$ in general.