Вопрос

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.

Это было полезно?

Решение

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top