networkx.utils.mapped_queue.MappedQueue

class MappedQueue(data=None)

MappedQueue 类实现了一个带有移除和更新优先级的最小堆。

最小堆使用 heapq 以及自定义的 _siftup 和 _siftdown 方法，以便通过一个由元素键控位置的额外字典来跟踪堆位置。最小元素可以在 O(1) 时间内弹出，新元素可以在 O(log n) 时间内推送，任何元素都可以在 O(log n) 时间内移除或更新。队列不能包含重复元素，尝试推送已存在于队列中的元素将不会有任何效果。

MappedQueue 补充了 Python 标准库中的 heapq 包。虽然 MappedQueue 旨在与 heapq 最大程度兼容，但它增加了元素移除、查找和优先级更新功能。

Parameters:

datadict 或 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

可以创建一个空的 MappedQueue ，或者可选地，给定一个初始元素和优先级的字典。方法 push 、 pop 、 remove 和 update 操作队列。

>>> 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']

也可以用列表或其他可迭代对象初始化 MappedQueue 。优先级假定为列表中项目的排序顺序。

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

如果元素不可比较，则会引发异常。

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

为了避免异常，使用字典为元素分配优先级。

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

__init__(data=None)

带有可更新优先级的优先队列类。

Methods

pop()	移除并返回队列中的最小元素。
push(elt[, priority])	将元素添加到队列中。
remove(elt)	从队列中移除一个元素。
update(elt, new[, priority])	将队列中的元素替换为新的元素。