Fibonacci Heap implementation

Hi everyone! I am implementing a Local Search algorithm using the Static Move Descriptors presented in https://www.sciencedirect.com/science/article/pii/S0305054810000535 . In order to do this I need to use a Fibonacci heap data structure. I could find any in Julia. Is there any implementation? If not what would you suggest instead of this?

Thank you,
Lefteris

Not sure there is DataStructures.jl try that

Are you sure a Fib. heap is actually required? Based on some light googling it seems performance of binary heaps is often better in practice.

Edit: also https://arxiv.org/pdf/1505.05033.pdf metions

Although the originaldescription of the algorithm advises using a Fibonacci Heap asits internal queue, it has been noted that in practice, a binary(ord-ary) heap implementation is significantly faster

1 Like

Have you tried just using a binary heap from datastructures?

You probably care about runtime, not provable complexity class. Constant factors are likely to swamp log factors for the heap, and your linked algorithm never merges two large heaps.

1 Like

Thank you! That’s true, the algorithm never merges. I am implementing it using a binary heap from DataStructures.jl right now!