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:

operation |
heapq (binary heap that comes with CPython) |
fibonacci-heap-mod |

find-min | O(1) | O(1) |

delete-min | O(log_{2}(n)) |
O(log_{2}(n)) |

insert | O(log_{2}(n)) |
O(1) |

decrease-key | O(log_{2}(n))(or rather it would be if it were supported?) |
O(1) |

merge | O(m*log_{2}(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.

3595

Back to Dan's tech tidbits

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