fibonacci-heap-mod is a Fibonacci Heap for (pure) Python - IOW, it's a theoretically nice priority queue. I ported it to Python from Java.

It runs on CPython 2.[67], CPython 3.[01234], Pypy 2.3.1, Pypy3 2.3.1 and Jython 2.7b3.

It passes pylint and pep8, and has thorough unit tests.

You can obtain it here.

Here's a big-O comparison between heapq and fibonacci-heap-mod:

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.


3595

Back to Dan's tech tidbits

You can e-mail the author with questions or comments: