How many comparisons will occur while performing a delete-min operation?

Category: QuestionsHow many comparisons will occur while performing a delete-min operation?
Editor">Editor Staff asked 4 weeks ago

How many comparisons will occur while performing a delete-min operation?
 
(a) d
 
(b) d-1
 
(c) d+1
 
(d) 1
 
Question is taken from Heap in chapter Heap of Data Structures & Algorithms I
 
The question was posed to me in quiz.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Right choice is (b) d-1
 
Easy explanation – Since, the delete-min operation is more expensive and the heap is shallow, the minimum of d elements can be found using d-1 comparisons.