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.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:

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.


Hits: 9053
Timestamp: 2024-03-28 09:46:55 PDT

Back to Dan's tech tidbits

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