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-fix the heap efficiently after the removal of the element?

O(d) but not O(1)
O(2d) but not O(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.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact to get access