The priorityq package provides a MappedQueue class implementing an
efficient minimum heap. The smallest element can be popped in O(1) time, new
elements can be pushed in O(log n) time, and any element can be removed or
updated in O(log n) time. The queue cannot contain duplicate elements and an
attempt to push an element already in the queue will have no effect.
MappedQueue complements the heapq package from the python standard library,
and has slightly different functionality. While MappedQueue is designed for
maximum compatibility with heapq, it is an independent implementation. The
priorityq package is free and open-source software and is released under
multiple licenses (see LICENSE for more info).
A MappedQueue can be created empty or optionally given an array of initial
elements. Calling push() will add an element and calling pop() will remove
and return the smallest element.
>>> q = MappedQueue([916, 50, 4609, 493, 237])
>>> q.push(1310)
True
>>> x = [q.pop() for i in range(len(q.h))]
>>> x
[50, 237, 493, 916, 1310, 4609]
Elements can also be updated or removed from anywhere in the queue.
>>> q = MappedQueue([916, 50, 4609, 493, 237])
>>> q.remove(493)
>>> q.update(237, 1117)
>>> x = [q.pop() for i in range(len(q.h))]
>>> x
[50, 916, 1117, 4609]