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$$

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License