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 for providing such a nice autoconf system for extension modules, and to Aaron Waters 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 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 into the queue with an associated priority of . Both items can be any python object, with the following restrictions: - must be comparable to all other priorities inserted. - 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 . 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 , 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 to be reduced. If is greater than the current priority associated with , 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 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