## Binary-Heap

 Question 1

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-ﬁx the heap efﬁciently after the removal of the element?

 A O(1) B O(d) but not O(1) C O(2d) but not O(d) D O(d 2d) but not O(2d)
Data-Structures       Binary-Heap       GATE 2016 [Set-1]       Video-Explanation
Question 1 Explanation:
→ If heap has n elements generally it takes O(n) to delete any arbitrary element.
→ Because we first need to find that element, O(n) time
Delete that element O(height) [deleting involves swapping particular element to rightmost leaf and then do heapify on that node].
**but here, we don't need to find that element, because in delete(i), i is index of that element.
Note: Delete time = O(height) = O(d)
There is 1 question to complete.

Register Now