سؤال

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