python - 从字典中创建优先级队列

Question

我有一个字典，其中键是节点，值是另一个字典。该字典将节点的父节点以及到达该节点的成本作为键。例如:

nodes = {0: {'cost': 0, 'parent': None}, 1: {'cost': 2, 'parent': 0}, 2: {'cost': 3, 'parent': 0}, 3: {'cost': 6, 'parent': 1}, 4: {'cost': 8, 'parent': 2}}

我想按成本顺序提取每个节点。第一个值(value)较低。我怎样才能做到呢？

Answer 1

从字典中的每个条目构建一个二元组，其第一个成员是要用作排序键的值。在本例中，这是条目内部字典中的 cost 属性。

元组的第二个成员将是原始字典中条目的键。将此键放入元组中将允许您在元组通过优先级队列后引用原始字典中的条目。

将这些元组收集到一个列表中。

您可以在一条语句中完成上述所有操作:

tuplist = [ (v['cost'], k) for k, v in nodes.items() ]

然后使用heapq模块将元组列表组织为最小堆:

import heapq

heapq.heapify(tuplist)

现在你可以对最小堆做任何你想做的事情。大概您会想要使用 heapq.heappop() 来按成本升序提取元组，然后使用提取的元组中的键来访问相应的字典条目并对其执行某些操作。看起来像这样:

while tuplist:
    tup = heapq.heappop(tuplist)
    key = tup[1]
    print key, nodes[key]

产生:

0 {'cost': 0, 'parent': None}
1 {'cost': 2, 'parent': 0}
2 {'cost': 3, 'parent': 0}
3 {'cost': 6, 'parent': 1}
4 {'cost': 8, 'parent': 2}