PQueue 0.1a - Extension priority-queue module
Andrew Snare
ajs@cs.monash.edu.au
Thu, 15 Jul 99 11:09:18 GMT
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/~earthpig/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 <james@daa.com.au>
for providing such a nice autoconf system for extension modules, and
to Aaron Waters <arw@pythonpro.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 <ajs@cs.monash.edu.au>
==
#!/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)
--
----------- comp.lang.python.announce (moderated) ----------
Article Submission Address: python-announce@python.org
Python Language Home Page: http://www.python.org/
Python Quick Help Index: http://www.python.org/Help.html
------------------------------------------------------------