An operator delete(i) for a binary heap data structure is to be designed to…
2016
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the ith 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 notO(1) - C.
O(2^d)andO(d) - D.
O(d 2^d)andO(2^d)
Attempted by 203 students.
Show answer & explanation
Correct answer: B
Key idea: delete the element at index i by replacing it with the last array element, then restore the heap by sifting that moved element up or down as needed.
Step 1 (O(1)): Copy the last element into index i and decrement the heap size. This replacement and array shrink cost constant time.
Step 2 (O(d)): Restore the heap property by either sifting the moved element up (swap with parent while heap property violated) or sifting it down (swap with the appropriate child). Each swap moves the element one edge, and at most d edges exist from the node to a leaf/root, so the restoration takes O(d) time in the worst case.
Conclusion: The replacement/removal step is O(1), and the re-fix (sift-up or sift-down) is O(d). For a heap with n nodes, d = O(log n), so this is O(log n) in terms of n.
A video solution is available for this question — log in and enroll to watch it.