An operator delete(i) for a binary heap data structure is to be designed to…
GATE · 2016 · CS · Set 1 · Computer Science & IT
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) but not O(d)
- D.
O(d 2^d) but not O(2^d)
Attempted by 305 students.
Show answer
Correct answer: B
The worked solution is available to enrolled students.
Video solution available to enrolled students.
Explore the full course: Iocl Engineers Officers Grade A Paper 2
Loading lesson…