find second smallest element in Fibonacci Heap

Posted by Longeyes on Programmers See other posts from Programmers or by Longeyes
Published on 2013-01-11T10:37:29Z Indexed on 2013/10/28 22:11 UTC
Read the original article Hit count: 319

Filed under:
|

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.

© Programmers or respective owner

Related posts about algorithms

Related posts about heap