The procedure FindMin() to find the minimum element and the procedure DeleteMin() to delete the minimum element in min heap take _________

Category: QuestionsThe procedure FindMin() to find the minimum element and the procedure DeleteMin() to delete the minimum element in min heap take _________
Editor">Editor Staff asked 4 weeks ago

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.

1 Answers
Editor">Editor Staff answered 4 weeks ago

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.