1

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.

4
  • 3
    a=extractMin; res=getMin; insert(a);return res;
    – ratchet freak
    Commented Jan 11, 2013 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
    Commented Jan 11, 2013 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
    Commented Jan 11, 2013 at 11:26
  • 1
    @ratchetfreak : Why not post your comment as an answer? :)
    – C.B.
    Commented Jun 18, 2013 at 9:29

1 Answer 1

Reset to default
0

a=extractMin; res=getMin; insert(a);return res;

[Folks: when answers are posted as comments, would you please add them as an answer and close the question. Thanks]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.