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

因为没有输出，所以很难运行代码。不过，我试了几件事：

在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。

回到输出问题，如果您指定希望输出的外观，我可以尝试帮助您更多。

Answer 2

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

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

所以对于你最初的问题：

Suppose I have 50 elements on the heap. And I want to change the value of element e3 from val = 53 to val = 0. So this is NOT the top element of the heap. I also don't want to remove other elements from the heap. How can I make such update?

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

• 检查dictionary以获取要更新的元素的索引（在检查元素是否在dictionary+相应堆中之后）
• 更新堆中的值
• 调用运行在O（N）中的heapq.heapify（heap）。或者，如果您知道您的更新将更新该值的+/-1，那么您可能只需将要更新的元素的位置与它上面或下面的元素交换。

编辑：这里有一个类似的问题，有更多的答案：How to update elements within a heap? (priority queue)