PQueue - Priority Queue

This is a priority queue I wrote in 2007.

It accepts a priority key, and returns items from larger to smaller.

Uses bisect.

# Complexity

- add(item) — O(log2 n)
- remove(item) — O(log2 n)
- __contains__(item) -> bool — O(log2 n)
- pop() —> item — O(1)

# Usage Example

>>> pqueue = snippets.get('pqueue') >>> p = pqueue.PriorityQueue(key=lambda x: x**2) >>> p.add(3) >>> p.add(10) >>> p.add(-5) >>> len(p) 3 >>> p.pop() 10 >>> p.add(4) >>> [p.pop() for i in range(len(p))] [-5, 4, 3] >>> len(p) 0

$$latest_version=0.1$$

page revision: 3, last edited: 02 Jun 2009 13:46