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:

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.

Hits: 9437

Timestamp: 2024-09-11 20:49:56 PDT

Back to Dan's tech tidbits

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