Saturday, September 6, 2014

Fibonacci Heap implementation in Pure Python


I've put a Pure Python Fibonacci Heap (priority queue) implementation at:

  1. https://pypi.python.org/pypi/fibonacci-heap-mod
  2. http://stromberg.dnsalias.org/~strombrg/fibonacci-heap-mod/
It passes pylint and pep8, is thoroughly unit tested, and runs on CPython 2.[67], CPython 3.[01234], Pypy 2.3.1, Pypy3 2.3.1 and Jython 2.7b3.

It's similar to the standard library's heapq module.  The main difference is Fibonacci heaps have better big-O for some operations, and also supports decrease-key without having to remove and re-add.

This Fibonacci heap implementation is also better abstracted than heapq.