An operator delete(i) for a binary heap data structure is to be designed to…

PYQ GATE 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 ?

  1. A.

    O(1)

  2. B.

    O(d)but not  O(1)

  3. C.

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

  4. D.

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

Attempted by 373 students.

Sign up free to check your answer

Sign up free

Explore the full course: Data Structures

Loading lesson…