Q37

MCQ2 marks, −0.67

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

(D)

$O(d \ 2^d)$ but not $O(2^d)$

Loading…