Project ForgeAn 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?
- AO(1)
- O(d) but not O(1)
- CO(2^d) but not O(d)
- DO(d·2^d) but not O(2^d)
Explanation
To delete node i, replace it with the heap's last element, then re-fix by either sifting it up (if it's now smaller/larger than its parent, for a min/max heap) or sifting it down (if it violates the heap property with its children). Either direction of movement can traverse at most the full depth d of the tree, and there exist configurations that genuinely require the full d steps (not O(1)), giving a tight bound of O(d).
Source: GATE CS 2016 (Session 1 / Set A) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.