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。 因此，这不是堆的顶部元素。 我也不想删除堆中的其他元素。 我该如何进行这样的更新操作？

- Ziva

---

使用heapq实现带有更新的优先队列的可能解决方案在文档中已经给出。 - Dan Getz

您的Element不可比较，因此我不确定您如何使用它们与heapq。您需要一个__lt__方法（或者使用内置类型，例如已经可比较的tuple）。 - Blckknght

哦，我明白了，在Python 2中，所有对象都是可比较的，只是如果您没有定义__cmp__或某些丰富的比较方法，则具有任意顺序。不过问题仍然有点荒谬，因为Element实例的val属性根本不影响其在堆中的位置。 - Blckknght

请参见以下链接：https://dev59.com/CHM_5IYBdhLWcg3wPAjT - qwr

这回答解决了你的问题吗？如何在Python的heapq中实现降低关键字的功能？ - qwr

Answer 1

这是一个旧问题，但以防将来有人看到此问题并正在寻找答案...

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

因此，对于您的原始问题：

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

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

• 查找字典以获取要更新的元素的索引（在检查元素是否在字典+相应堆之后）
• 更新堆中的值

执行O(N)时间复杂度的heapq.heapify(heap)函数。或者，如果你知道更新操作只会将元素的值加减1，那么你可以尝试与相邻的元素交换位置来更新所需元素的值。

编辑：这里有一个类似的问题，有更多答案：如何在堆（优先队列）中更新元素？

- Joyce Lee

---

关于"调用heapq.heapify(heap)的时间复杂度为O（N）"：重新平衡只需要O（log n）或树的最大深度，这个过程有点像你建议的交换父/子位置。然而，“通过+/-1更新值”的说法在某些情况下是误导性的或者是错误的。特别地，如果优先级值不必是唯一的，或者如果优先级值是除整数以外的其他类型，比如浮点数，那么这种说法就是错误的。 - rocky

在使用堆的同时，如何保持将元素映射到其索引的字典与堆同步？ - qwr

Answer 2

在确定所需元素的索引后，您可以在整个堆上调用heapify以恢复堆。确定索引是困难的部分，因为您需要在每次堆操作之后跟踪每个元素在堆中的位置，我认为最简单的方法是自定义堆实现。

import heapq
h = [[1, "A"], [65, "B"], [53, "C"], [67, "D"]]
heapq.heapify(h)
# assume you know index of element C is 2
h[2][0] = 0
heapq.heapify(h)

有趣的是，CPython的heapq实现内部有_siftup和_siftdown两种方法。在实践中，使用_siftup应该比在整个堆上调用heapify更快，但在时间复杂度上不如后者，因为heapify将调用_siftup n/2次，但只有log(n)个元素实际上需要交换。

- qwr

---

不确定 2021/10 的状态如何，但是目前 _siftup 的时间复杂度（提交记录：https://github.com/python/cpython/commit/d7d4a0583ff8bd7c5b614490ba22e88da23b5b84）为 O(log n)，而 heapify 为 O(n)。 - Adam Hoelscher

Answer 3

由于没有输出，运行您的代码很困难。 但是，我尝试了一些方法：

在heapq模块中，heap[0]总是被指定为最小项。 在您的情况下，1是最小项。 因此，将此值从1更改为5理论上应该很容易。 我尝试了heapq.heappop(heap)，它应该返回最小值。 因此，正如您在问题中所说，“我想更新我不知道哪个元素的val，因为它与名称First相结合”，这种方法会自动获取最小值（我假设您想替换1，因为它是最小值）。 但是，当我尝试运行您的代码时，我收到了<__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。

回到输出问题，如果您指定您想要的输出样式，我可以尝试更多地帮助您。

- warship

---

你误解了我的问题。我进行了编辑以更好地解释我的问题，并尝试展示如何打印元素信息。代码运行良好。 - Ziva