This is the first release of a module I've just written, released under the LGPL. It is available for download at: http://www.pigpond.com/%7Eearthpig/PQueue-0.1a.tar.bz2
From the documentation included with the release:
PQueue Extension Module for Python - 0.1a =========================================
This C extension implements a priority-queue object using a fibonacci heap as the underlying data structure. This data structure supports the following operations with the given amortized time-complexity:
- insert: O(1) - find-min: O(1) - extract-min: O(lg N) - decrease-key: O(1) - increase-key: O(lg N) (== delete, insert) - delete: O(lg N) (== decrease-key, extract-min)
This asymptotic behaviour compares favourably to more traditional structures such as binomial heaps, at the cost of slightly higher constant overheads.
This is the first public release of this extension -- feedback is both welcome and encouraged. Thanks must go to James Henstridge firstname.lastname@example.org for providing such a nice autoconf system for extension modules, and to Aaron Waters email@example.com for providing the PyModules FAQ resource and his pq3.py module (a slightly modified version of which is included in this distribution for benchmarking purposes).
- Andrew Snare firstname.lastname@example.org == #!/usr/bin/env python print(lambda s:s+"("+`s`+")")\ ('#!/usr/bin/env python\012print(lambda s:s+"("+`s`+")")\\012') print(lambda x:x%`x`)('print(lambda x:x%%`x`)(%s)')
For the web thingy: <P><A HREF="http://www.pigpond.com/~earthpig/PQueue-0.1a.tar.bz2">PQueue 0.1a</A> - fast priority-queue extension module implemented in C. (15-Jul-99)