Pregunta

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.

¿Fue útil?

Solución

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

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top