GATE | GATE-CS-2016 (Set 1) | Question 47

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?
(A) O(1)
(B) O(d) but not O(1)
(C) O(2d) but not O(d)
(D) O(d2d) but not O(2d)
Answer: (B)

Explanation:

For this question, we have to slightly tweak the delete_min() operation of the heap data structure to implement the delete(i) operation. The idea is to empty the spot in the array at the index i (the position at which element is to be deleted) and replace it with the last leaf in the heap (remember heap is implemented as complete binary tree so you know the location of the last leaf), decrement the heap size and now starting from the current position i (position that held the item we deleted), shift it up in case newly replaced item is greater than the parent of old item  (considering max-heap).  If it’s not greater than the parent, then percolate it down by comparing with the child’s value. The newly added item can percolate up/down a maximum of d times which is the depth of the heap data structure.

Thus we can say that complexity of delete(i) would be O(d) but not O(1).

Leave a Reply

Your email address will not be published. Required fields are marked *