It runs on CPython 2.7, CPython 3.[0123456], Pypy 5.10.0, Pypy3 5.10.0 and Jython 2.7.
It passes pylint, pyflakes, pycodestyle, and pydocstyle; and has thorough unit tests.
You can obtain it here.
Here's a big-O comparison between heapq and fibonacci-heap-mod:
operation |
heapq (binary heap that comes with CPython) |
fibonacci-heap-mod |
| find-min | O(1) | O(1) |
| delete-min | O(log2(n)) | O(log2(n)) |
| insert | O(log2(n)) | O(1) |
| decrease-key | O(log2(n)) (or rather it would be if it were supported?) |
O(1) |
| merge | O(m*log2(n+m)) (or rather it would be if it were supported?) |
O(1) |
One virtue of a Fibonacci Heap is that it is lazy; it puts off organizing the heap until necessary. This can significantly improve the big-O of some algorithms. Also decrease-key and merge are nice.
I was more than a little (but pleasantly) surprised to hear that this heap implementation can perform reasonably well, even outside of its laziness.
BTW, the priorities can be int's and/or float's, but I haven't tested it with decimal.Decimal or fractions.Fraction. I was a little concerned they wouldn't compare to float('inf') or float('-inf') correctly, but after a little experimentation in a REPL, I've concluded it's possible they will work.
See also this list of datastructures I've worked on.
You can e-mail the author with questions or comments: