Fibonacci Heap implementation

Specific Domains Optimization (Mathematical)
1

Hi everyone! I am implementing a Local Search algorithm using the Static Move Descriptors presented in A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem - ScienceDirect . 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

2

Not sure there is DataStructures.jl try that

3

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
4

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
5

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