# Fibonacci Heap implementation

**URL:** <https://discourse.julialang.org/t/fibonacci-heap-implementation/18412>\
**Category:** Optimization (Mathematical)\
**Tags:** optimization\
**Created:** [December 7, 2018, 9:35am UTC](https://discourse.julialang.org/t/fibonacci-heap-implementation/18412 "2018-12-07T09:35:21Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lefteris\_Manousakis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lefteris_manousakis/32/10832_2.png) [@Lefteris\_Manousakis](https://discourse.julialang.org/u/Lefteris_Manousakis)\
**Post date:** [December 7, 2018, 9:35am UTC](https://discourse.julialang.org/t/fibonacci-heap-implementation/18412/1 "2018-12-07T09:35:21Z")

</div>

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](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

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [December 7, 2018, 9:37am UTC](https://discourse.julialang.org/t/fibonacci-heap-implementation/18412/2 "2018-12-07T09:37:17Z")

</div>

Not sure there is DataStructures.jl try that

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [December 7, 2018, 12:57pm UTC](https://discourse.julialang.org/t/fibonacci-heap-implementation/18412/3 "2018-12-07T12:57:08Z")

</div>

> [@Lefteris\_Manousakis](#):
>
> Fibonacci heap

Are you sure a Fib. heap is actually required? Based on [some light googling](https://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently) it seems performance of binary heaps is often better _in practice_.

Edit: also [https://arxiv.org/pdf/1505.05033.pdf](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

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [December 7, 2018, 1:05pm UTC](https://discourse.julialang.org/t/fibonacci-heap-implementation/18412/4 "2018-12-07T13:05:27Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Lefteris\_Manousakis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lefteris_manousakis/32/10832_2.png) [@Lefteris\_Manousakis](https://discourse.julialang.org/u/Lefteris_Manousakis)\
**Post date:** [December 7, 2018, 1:07pm UTC](https://discourse.julialang.org/t/fibonacci-heap-implementation/18412/5 "2018-12-07T13:07:20Z")

</div>

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