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 <
[email protected]>
for providing such a nice autoconf system for extension modules, and
to Aaron Waters <
[email protected]> 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 <
[email protected]>
Compiling and Installing
========================
Compiling should be as simple as:
1) Unpacking the distribution (hopefully complete if you are reading
this);
2) % ./configure
3) % make
Installing should be as simple as:
4) # make install
Using the PQueue Extension
==========================
The priority-queue object (PQueue) is made available using something
like:
>>> from pqueue import PQueue
A priority-queue can then be instantiated using something like:
>>> pq = PQueue()
The constructor takes no arguments and runs in O(1) amortized
time. PQueue methods are:
PQueue.insert(priority,data):
Inserts <data> into the queue with an associated
priority of <priority>. Both items can be any python
object, with the following restrictions:
- <priority> must be comparable to all other priorities
inserted.
- <data> must be hashable. If the data is not unique
(and has been previously attached to an element in
the queue) then the mapping interface described
below is not available for <data>.
This call runs in O(1) amortized time.
PQueue.peek():
Returns a (priority,data) tuple containing the element
in the queue with the lowest priority, but does not
remove the element from the queue. These should be
considered immutable (even if they are not so).
This call runs in O(1) amortized time.
PQueue.pop():
Returns a (priority,data) tuple containing the element
in the queue with the lowest priority, and extracts it
from the queue.
This call runs in O(lg N) amortized time.
In addition, PQueue objects support a mapping interface such that:
len(pq):
Returns the number of elements currently in the queue.
This call runs in O(1) amortized time.
pq[data]
Returns the priority associated with <data>, assuming
it has already been inserted in the queue (otherwise
KeyError is raised).
This call runs in O(1) amortized time.
pq[data] = priority
Allows the priority associated with <data> to be
reduced. If <priority> is greater than the current
priority associated with <data>, ValueError is raised.
This call runs in O(1) amortized time if the new
priority is less than or equal to the current
priority. If the new priority is greater than the
current one, a delete/insert is done which means the
call runs in O(lg N) amortized time.
del pq[data]
Deletes the element associated with <data> from the
queue.
This call runs in O(lg N) amortized time.
Feedback regarding this interface is most welcome.
Bugs
====
Since this is the initial release, there is sure to be bugs
lurking. While every effort has been made to find them and hit them
with a big bat, the complexity of the underlying data structures makes
it very difficult to test the module fully. If anomolies are noticed,
I'd appreciate a note (including how to reproduce the anomoly) since
debugging this beast will be rather difficult.
Contacting the Author
=====================
The author of this package can be reached at:
Andrew Snare <
[email protected]>
