+1 vote
in Data Structures & Algorithms I by (88.2k points)
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 Answer

+1 vote
by (672k points)
selected by
 
Best answer
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.

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.

Categories

...