更新优先级队列

Question

当项目是整数还是字符串时，PriorityQueue的不同行为让我非常困惑。但在解决这个问题之前，我想了解以下行为（使用项作为整数）

假设我有一个包含以下数据的优先级队列（对于每个元素，第一个值是优先级，第二个值是项）：

图1：

执行以下命令后：

pq.put(pq.get())

元素的排序如下所示：

图2：

为什么有些元素改变了位置？分拣是怎么回事

下面是从调试器中复制这些屏幕截图的代码：

from sys import maxsize
from queue import PriorityQueue

items = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 15, 16]
INFINITY = maxsize
minDist = {k: INFINITY for k in items}
minDist[3] = 0

pq = PriorityQueue(len(minDist))

for v in minDist.keys():
    pq.put([minDist[v], v])

# At this point, pq has the elements as shown in Image 1

pq.put(pq.get())

# Now, pq has elements scrambled as shown in Image 2

经验教训

根据下面的调查和讨论，对pq.put(pq.get())的每次调用都将重新排列优先级队列数据结构。目前还不清楚是否有办法控制这种情况。如果你知道怎么做，请在下面发表评论

我的具体问题似乎与物品的分类有关。如图1和图2所示，项目是1到17之间的整数。如果将它们转换为字符串（即"1"、"2"、"17"），则我得到的行为与原始代码中的主函数不同。但是，如果我对每个键使用zfill(2)，因此我有"01"，"02"，"17"，"17"，我可以得到与使用整数相同的最终结果

Answer 1

我不清楚您显示的屏幕截图中发生了什么，但下面显示了一个与解释器的示例会话，该会话试图用稍微不同的方法重现问题：

Python 3.8.2 (tags/v3.8.2:7b3ab59, Feb 25 2020, 23:03:10) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>> import math, pprint, queue
>>> min_dist = {x: math.inf for x in range(1, 17)}
>>> min_dist[3] = 0
>>> pq = queue.PriorityQueue(len(min_dist))
>>> for key, value in min_dist.items():
    pq.put((value, key))


>>> pq_items = []
>>> while not pq.empty():
    pq_items.append(pq.get())


>>> pprint.pprint(pq_items)
[(0, 3),
 (inf, 1),
 (inf, 2),
 (inf, 4),
 (inf, 5),
 (inf, 6),
 (inf, 7),
 (inf, 8),
 (inf, 9),
 (inf, 10),
 (inf, 11),
 (inf, 12),
 (inf, 13),
 (inf, 14),
 (inf, 15),
 (inf, 16)]
>>> for key, value in min_dist.items():
    pq.put((value, key))


>>> pq.put(pq.get())
>>> pq_items.clear()
>>> while not pq.empty():
    pq_items.append(pq.get())


>>> pprint.pprint(pq_items)
[(0, 3),
 (inf, 1),
 (inf, 2),
 (inf, 4),
 (inf, 5),
 (inf, 6),
 (inf, 7),
 (inf, 8),
 (inf, 9),
 (inf, 10),
 (inf, 11),
 (inf, 12),
 (inf, 13),
 (inf, 14),
 (inf, 15),
 (inf, 16)]
>>> 

您可能希望调整代码，以使用类似的方法来获得所需的内容。如果您在处理字符串时遇到问题，那么您可能需要检查如果将元素放入列表并进行排序，元素的排序方式