Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I need to describe an algorithm that finds the second smallest element in a Fibonacci-Heap using the Operations: Insert, ExtractMin, DecreaseKey and GetMin. The last one is an algorithm previously implemented to find and return the smallest element of the heap.

I thought I'd start by extracting the minimum, which results in its children becoming roots. I could then use GetMin to find the second smallest element. But it seems to me that I'm overlooking other cases because I don't know when to use Insert and DecreaseKey, and the way the question is phrased seems to suggest I should need them.

share|improve this question
2  
a=extractMin; res=getMin; insert(a);return res; –  ratchet freak Jan 11 '13 at 10:49
    
Why do I need to insert a again? And also, does it not matter that I still haven't used DecreaseKey then? –  Longeyes Jan 11 '13 at 11:24
    
only if you want to keep the heap unchanged after the call to getSecondMin, and no it doesn't matter that you didn't use it –  ratchet freak Jan 11 '13 at 11:26
    
oh okay! thanks XD –  Longeyes Jan 11 '13 at 11:27
1  
@ratchetfreak : Why not post your comment as an answer? :) –  C.B. Jun 18 '13 at 9:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.