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
algorithms
|heap
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