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 兼容，但它增加了元素移除、查找和优先级更新的功能。

参数:

data字典或可迭代对象

参考文献

[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.

示例

可以创建一个空的 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)

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

方法

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