Saturday, September 6, 2014

Fibonacci Heap implementation in Pure Python

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

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.