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., CPython 3., 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.