Heappop() 不是不变的
Heappop() not invariant
当我使用 heapq.heappop(queue) 时，列表中的第一项被弹出，但其余列表被修改。我怎样才能防止这种情况发生？ （注意下面包含 'r' 和 'o' 的元组）
这是我的调试输出：
队列：PQ:[(1, 2, 'z'), (1, 3, 't'), (2, 4, 'r'), (2, 5 , 'o'), (2, 6, 'f')]
弹出前排队：[(1, 2, 'z'), (1, 3, 't'), (2, 4, 'r'), (2, 5 , 'o'), (2, 6, 'f')]
priority, counter, node = heapq.heappop(queue)
项目 returned: (1, 2, 'z')
弹出队列后：[(1, 3, 't'), (2, 5, 'o'), (2, 4, 'r'), (2, 6, 'f')]
计数器应该确保较早添加的节点更接近队列[0]。
弹出后我的队列不只是弹出堆[0]，它重新排列并将包含'o' 的元组放在包含'r' 的元组之前。它们的优先级相同（2），但它们的计数器分别为 5 和 4，因此，它们以错误的顺序重新排列。
Inst heappop() 只假设 return heap[0] 并将队列中的其他所有内容向上移动？我怎样才能防止这种重新排列？
这是堆的正常预期行为。堆的任意元素之间没有隐含的顺序：唯一不变的是每个节点都小于其 children 中的任何一个。一旦你的 (1,3,'t') 元素被弹出，(2,4,'r') 将被选为新的根，因为它是前根的两个 children 中较小的一个；它相对于 (2,5,'o') 的排序直到那个时间点才相关。换句话说，根是唯一的元素，您可以根据它在堆中的索引来说明它的值。
如果您想要一个始终完全排序的列表，您需要 bisect 模块，而不是 heapq。当然性能会差很多。
当我使用 heapq.heappop(queue) 时，列表中的第一项被弹出，但其余列表被修改。我怎样才能防止这种情况发生？ （注意下面包含 'r' 和 'o' 的元组）
这是我的调试输出：
队列：PQ:[(1, 2, 'z'), (1, 3, 't'), (2, 4, 'r'), (2, 5 , 'o'), (2, 6, 'f')]
弹出前排队：[(1, 2, 'z'), (1, 3, 't'), (2, 4, 'r'), (2, 5 , 'o'), (2, 6, 'f')]
priority, counter, node = heapq.heappop(queue)
项目 returned: (1, 2, 'z') 弹出队列后：[(1, 3, 't'), (2, 5, 'o'), (2, 4, 'r'), (2, 6, 'f')]
计数器应该确保较早添加的节点更接近队列[0]。
弹出后我的队列不只是弹出堆[0]，它重新排列并将包含'o' 的元组放在包含'r' 的元组之前。它们的优先级相同（2），但它们的计数器分别为 5 和 4，因此，它们以错误的顺序重新排列。
Inst heappop() 只假设 return heap[0] 并将队列中的其他所有内容向上移动？我怎样才能防止这种重新排列？
这是堆的正常预期行为。堆的任意元素之间没有隐含的顺序：唯一不变的是每个节点都小于其 children 中的任何一个。一旦你的 (1,3,'t') 元素被弹出，(2,4,'r') 将被选为新的根，因为它是前根的两个 children 中较小的一个；它相对于 (2,5,'o') 的排序直到那个时间点才相关。换句话说，根是唯一的元素，您可以根据它在堆中的索引来说明它的值。
如果您想要一个始终完全排序的列表，您需要 bisect 模块，而不是 heapq。当然性能会差很多。