代码之家  ›  专栏  ›  技术社区  ›  Leo

Heappop()不是不变量

  •  0
  • Leo  · 技术社区  · 8 年前

    当我使用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 回复  |  直到 8 年前
        1
  •  2
  •   jasonharper    8 年前

    这是堆的正常预期行为。堆的任意元素之间没有隐含的排序:唯一不变的是每个节点都小于其任何一个子节点。一旦你 (1,3,'t') 元素弹出, (2,4,'r') 将被选为新根,因为它是前根的两个孩子中较小的一个;其排序相对于 (2,5,'o')

    如果您想要一个始终处于完全排序顺序的列表,那么您需要 bisect 模块,非 heapq