The procedure FindMin() to find the minimum element and the procedure DeleteMin() to delete the minimum element in min heap take _________
(a) logarithmic and linear time constant respectively
(b) constant and linear time respectively
(c) constant and quadratic time respectively
(d) constant and logarithmic time respectively
The origin of the question is Heap topic in chapter Heap of Data Structures & Algorithms I
This question was posed to me in exam.
The correct option is (d) constant and logarithmic time respectively
The best I can explain: In the min heap, the root is the maximum element in the tree. So, locating it takes constant time, but deleting it takes logarithmic time. Because after deleting it, the root is replaced with last element and then the procedure to maintain the min ordering is invoked.