11

Is there a Fibonacci heap/priority queue available for Haskell? (Or even an asymptotically better one?) I found a list of various priority queue implementations in this question, but I couldn't find if any of them satisfies the amortized running time of Fibonacci heaps:

  • Find-minimum is O(1) amortized time.
  • Operations insert, decrease key, and merge (union) work are O(1) amortized time.
  • Operations delete and delete minimum are O(log n) amortized time.

See the comparison of theoretic bounds.

Community
  • 1
  • 1
Petr
  • 62,528
  • 13
  • 153
  • 317
  • 1
    It's possible that no production code exists, as the constant factors generally make Fibonacci heaps slower than binomial heaps for reasonable-sized datasets, despite the theoretical asymptotic advantage. – Oliver Charlesworth May 29 '13 at 09:42
  • @OliCharlesworth Interesting, could you give a rough estimate for what sizes Fibonacci heaps become advantageous? – Petr May 29 '13 at 09:43
  • TBH, this is somewhat out of my area; I've only read about such disadvantages (see e.g. [CLRS](http://en.wikipedia.org/wiki/CLRS)). Don't quote me on it ;) – Oliver Charlesworth May 29 '13 at 09:46
  • http://hackage.haskell.org/package/pqueue is fairly optimized. – Louis Wasserman May 29 '13 at 19:18

1 Answers1

9

Not a Fibonacci Heap, but just as good: heaps by Edward Kmett based on the Brodal/Okasaki persistent variant of Brodal heaps.

Philip JF
  • 28,199
  • 5
  • 70
  • 77