当我使用heapq时。heappop(queue),弹出列表上的第一项,但修改其余列表。我该如何防止这种情况?(注意下面包含“r”和“o”的元组)
Pop前的队列:[(1,2,'z',(1,3,'t',(2,4,'r',(2,5,'o',(2,6,'f')]
priority, counter, node = heapq.heappop(queue)
返回的项目:(1,2,'z') Pop后的队列:[(1,3,'t’,(2,5,'o’,(2,4,'r’,(2,6,'f’)]
计数器应该确保节点的早期添加更接近队列[0]。
这是堆的正常预期行为。堆的任意元素之间没有隐含的排序:唯一不变的是每个节点都小于其任何一个子节点。一旦你 (1,3,'t') 元素弹出, (2,4,'r') 将被选为新根,因为它是前根的两个孩子中较小的一个;其排序相对于 (2,5,'o')
(1,3,'t')
(2,4,'r')
(2,5,'o')
如果您想要一个始终处于完全排序顺序的列表,那么您需要 bisect 模块,非 heapq
bisect
heapq