Question

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(d2^d) but not O(2^d)

Answer 1

Correct Answer - Option 2 : O(d) but not O(1)

STEPS:

1)  delete (i) will delete the element at ith index in the binary heap in O (1) time.

2) But, we have to fill the empty position with the last node of the heap.

3) Last node of the heap can be easily found in O (1) time and replace empty position with this node.

4) After this, there is need to heapify the binary heap which will take  O (depth of heap tree).

5) Depth of heap tree is log n if n is number of elements in the heap.

6) But, in question it is given that depth is d. So, this delete (i) will take O (d) time not O(1)