python - 更新 PriorityQueue

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"), 我在原始代码中得到了与 main 函数不同的行为。但是，如果我为每个键使用 zfill(2)，那么我有 "01"、"02"，...， “17”，我可以获得与使用整数时相同的最终结果。

Answer 1

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

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

您可能希望调整您的代码以使用类似的方法来获取您正在寻找的内容。如果您在使用字符串时遇到问题，那么您可能想要检查如果将元素放入列表中然后进行排序，它们将如何排序。