在Python中，如何实现minpriority队列，该队列在更改其成员的优先级时保持堆不变？

Question

我想用堆数据结构实现Dijkstra的最短路径算法。为此，我正在寻找一个堆，当您更改元素的优先级时，它会根据需要自动上下筛选其成员。在

到目前为止，我已经尝试过queue.PriorityQueue和Stutzbach的heapdict，但从下面的测试中看，似乎都没有这个属性：

import queue
from heapdict import heapdict
import pytest

class Node(object):
    def __init__(self, d):
        self.d = d

    def __lt__(self, other):
        return self.d < other.d


def test_priority_queue():
    node1 = Node(d=5)
    node2 = Node(d=10)
    Q = queue.PriorityQueue()
    Q.put(node1)
    Q.put(node2)
    node2.d = 2
    assert Q.get().d == 2       # Fails because 5 != 2

def test_heapdict():
    node1 = Node(d=5)
    node2 = Node(d=10)
    hd = heapdict()
    hd[1] = node1
    hd[2] = node2
    node2.d = 2
    index, node = hd.popitem()
    assert node.d == 2          # Fails because 5 != 2


if __name__ == "__main__":
    pytest.main([__file__])

当我将node2的优先级更新为2而不是{}时，它应该自动移动到堆的顶部，以便get/popitem方法返回它。我想创建一个数据结构，这样类似的测试就能通过。在

不过，我正努力想出一个如何实现这一目标的高层次想法。它可能应该跟在observer pattern后面，并使用一个property属性，但是具体怎么做呢？在

更新

执行类似操作的对象是pqdict。但是，根据its documentation的说法，它也不适用于可变对象：

Value mutability. If you use mutable objects as values in a pqdict, changes to the state of those objects can break the priority queue. If this does happen, the data structure can be repaired by calling pq.heapify(). (But you probably shouldn’t be using mutable values in the first place.)