networkx.utils.mapped_queue.MappedQueue

class MappedQueue(data=None)

The MappedQueue class implements a min-heap with removal and update-priority.

The min heap uses heapq as well as custom written _siftup and _siftdown methods to allow the heap positions to be tracked by an additional dict keyed by element to position. 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. While MappedQueue is designed for maximum compatibility with heapq, it adds element removal, lookup, and priority update.

Parameters:

datadict or iterable

References

[1]

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to algorithms second edition.

[2]

Knuth, D. E. (1997). The art of computer programming (Vol. 3). Pearson Education.

Examples

A MappedQueue can be created empty, or optionally, given a dictionary of initial elements and priorities. The methods push, pop, remove, and update operate on the queue.

>>> colors_nm = {'red':665, 'blue': 470, 'green': 550}
>>> q = MappedQueue(colors_nm)
>>> q.remove('red')
>>> q.update('green', 'violet', 400)
>>> q.push('indigo', 425)
True
>>> [q.pop().element for i in range(len(q.heap))]
['violet', 'indigo', 'blue']

A MappedQueue can also be initialized with a list or other iterable. The priority is assumed to be the sort order of the items in the list.

>>> q = MappedQueue([916, 50, 4609, 493, 237])
>>> q.remove(493)
>>> q.update(237, 1117)
>>> [q.pop() for i in range(len(q.heap))]
[50, 916, 1117, 4609]

An exception is raised if the elements are not comparable.

>>> q = MappedQueue([100, 'a'])
Traceback (most recent call last):
...
TypeError: '<' not supported between instances of 'int' and 'str'

To avoid the exception, use a dictionary to assign priorities to the elements.

>>> q = MappedQueue({100: 0, 'a': 1 })

__init__(data=None)

Priority queue class with updatable priorities.

Methods

pop()	Remove and return the smallest element in the queue.
push(elt[, priority])	Add an element to the queue.
remove(elt)	Remove an element from the queue.
update(elt, new[, priority])	Replace an element in the queue with a new one.