Programming and Data Structures · Binary Heaps · 2 marks · Multiple choice
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?
To delete the item at index $i$, move the last element of the heap into that position. Then it may need to move up or down along one root-to-leaf path to restore the heap property, which takes at most $d$ swaps. That is $O(d)$, and it is not $O(1)$ in general.
More Binary Heaps questions
GATE 2014 CS (CS2) Q22– A max-heap priority queue initially has level order 10,8,5,3,2. Insert 1 then 7. Find the…
GATE 2016 CS (CS2) Q44– A complete binary min-heap contains each integer 1 through 1023 once. Root depth is zero.…
GATE 2011 CS Q33– A max-heap has parent values at least their children’s values. Which displayed tree is a…
GATE 2015 CS (CS2) Q22– A complete binary tree has max-heaps as the left and right subtrees of its root. Which…
GATE 2015 CS (CS3) Q30– Find the minimum number of interchanges needed to convert the level-order array…
GATE 2021 CS (CS2) Q12– A binary min-heap of n elements is stored in an array. Find the worst-case complexity of…