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:

>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