Python:更新heapq中元素的值

Question

如果我有一个heapq,其中包含一些元素,如:

import heapq


class Element(object):
    def __init__(self, name, val):
        self.name = name
        self.val = val

if __name__ == "__main__":
    heap = []
    e1 = Element('A', 1)
    e2 = Element('B', 65)
    e3 = Element('C', 53)
    e4 = Element('D', 67)
    ...

    heapq.heappush(heap, e1)
    heapq.heappush(heap, e2)
    heapq.heappush(heap, e3)
    heapq.heappush(heap, e4)
    ...

    #IF I want to take elements from the heap and print them I will call:
    while heap:
        new_e = heapq.heappop(heap)
        print new_e.name + ' ' + str(new_e.val)

假设我在堆上有50个元素.我想将元素e3的值从val = 53更改为val = 0.所以这不是堆的顶部元素.我也不想从堆中删除其他元素.我该怎么做这样的更新？

Answer 1

这是一个老问题，但万一将来有人看到这个并正在寻找答案......

Python3 的 heapq 新实现包括一些关于如何更新堆元素的有用注释，本质上是将其用作优先级队列。 https://docs.python.org/3.5/library/heapq.html#priority-queue-implementation-notes 本质上，您可以创建一堆元组，Python 将根据元组的顺序比较来评估优先级。由于 Python 中的堆基本上只是一个标准列表，顶部使用了 heapq 接口，因此文档建议可能有一个额外的字典，它将堆值映射到堆（列表）中的索引。

所以对于你原来的问题：

假设堆上有 50 个元素。我想将元素 e3 的值从 val = 53 更改为 val = 0。所以这不是堆的顶部元素。我也不想从堆中删除其他元素。我怎样才能进行这样的更新？

按照上述逻辑更新堆中元素的基本步骤是：

• 检查字典，获取要更新的元素的索引（检查该元素是否在字典+对应的堆中后）
• 更新堆中的值
• 调用 heapq.heapify(heap) ，其运行时间为 O(N)。或者，如果您知道更新会将值更新 +/- 1，则可能只需将要更新的元素的位置与其上方或下方的元素交换即可。

编辑：这是一个类似的问题，有更多答案：How to update elements inside a heap? （优先队列）

Answer 2

由于没有输出，因此很难运行您的代码。但是，我尝试了一些事情：

在 heapq 模块中，heap[0]始终指定最小的项。就您而言，1 是最小的项目。因此，理论上将该值从 1 更改为 5 应该很容易。我尝试了heapq.heappop(heap)哪个应该返回最小值。因此，正如您在问题中所说，“我想更新元素的 val，我不知道它依次是哪个”，此方法会自动为您获取最小值（我从您的问题中假设您想要替换 1因为它是最小值，因为它与名称结合在一起First）但是，当我尝试自己运行您的代码时，我收到了这样的信息，<__main__.Element object at 0x103c15dd0>因此您应该尝试修复您的代码，以便可以打印输出，同样的情况也适用print heap[0]，相同的错误类型。然后，一旦您不再收到此类错误，请在代码块末尾尝试：

s = heapq.heappop(heap)

print heapq.heapreplace(5, s)

使用这种方法，我收到以下错误：TypeError: heap argument must be a list 因此，如果您能弄清楚如何将 s 转换为列表，那么这应该可行。也许有人可以编辑我的答案以添加此代码。

希望这可以帮助。

自编辑：

将其添加到代码块的末尾，[] 将其转换为列表，这就是 heapq 想要的输入。

s = heapq.heappop(heap)

print heapq.heapreplace([5], [s])

这将在输出中返回值 5。

回到输出问题，如果你指定你想要的输出是什么样子，我可以尝试为你提供更多帮助。