1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
PQueue Extension Module for Python - 0.2
=========================================
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 second release of this extension -- the first release was
very stable with the exception of one glaring bug which has now been
fixed. 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@pigpond.com>
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
Sets the priority associated with <data> to <priority>.
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
====
There may be bugs lurking in this release although the package has been
fairly extensively tested. Unfortunately 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 <ajs@pigpond.com>
|
