An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node.

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 elemts? 

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)

2Comments
gaurav vishwakarma @gauravvishwakar
19 Jul 2017 05:51 pm

O(2d) but not O(d)

Sumit Verma @sumitkgp
19 Jul 2017 10:15 pm

height of heap either it is min heap or max heap O(logn) or O(d);
delete the i th node then re-fix O(logn) or O(d)  but not O(1) .
Becasue tree not contain only one element also complexity of heap re-fix is O(logn) for avg or worst and O(1) for  best case;

so answer is B.