Software

As a computer scientist, I occasionally write software. Some things that I have written in my spare time get posted here.

• A Fibonacci heap for Python

  This is a C extension to Python providing a priority queue implemented as a Fibonacci heap, which allows decrease-key operations in amortized constant time. (Python's heapq module is a poor solution for any priority queue that requires the ability to decrease keys on existing heap entries -- as in, for instance, an A* search. It is necessary, using heapq, to re-heapify the entire list, a linear-time operation.)

  This software could generously be described as "alpha", since error-checking is minimal, functionality is limited, and I have had no opportunity to perform extensive testing on it; however, an A* search over approximately 360,000 nodes runs twenty seconds faster on my MacBook Pro using the Fibonacci heap than a heapq list. Comparable results are obtained on Linux workstations. I have run searches with this extension and verified its basic functionality on Mac OS X 10.5 with Python 2.6, and on RedHat Linux with Python 2.5 and 2.6. I have not tested it on Windows or with Python 3.0; if anyone does so, I would appreciate knowing the results.

  This software may be used under the MIT license; it is freely usable for any purpose, commercial or non-commercial, open or closed. If you discover bugs or have bugfixes or improvements, I encourage you to contact me and let me know about them.

  Download distutils source packages for *nix/Mac OS X or Windows.