Python：更新heapq中的元素值

19 投票

3 回答

26432 浏览

提问于 2025-04-18 17:21

假设我有一个堆（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的值从53改成0。这个元素e3并不是堆顶的元素。而且我也不想把其他的元素从堆里移除。请问我该怎么更新这个值呢？

数据结构优先队列元素更新 heap

3 个回答

运行你的代码很困难，因为没有输出。不过，我尝试了一些方法：

在heapq模块中，heap[0]总是指向最小的那个元素。在你的例子里，1就是最小的元素。所以，把这个值从1改成5理论上应该很简单。我试了heapq.heappop(heap)，这个方法应该会返回最小的值。因此，正如你在问题中提到的“我想更新我不知道的元素的值”，这个方法会自动给你最小的值（我假设你想替换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。

回到输出的问题，如果你能具体说明你希望输出是什么样子的，我可以尝试更好地帮助你。

回答于 2025-04-18 由 Python大师

分享举报

在找到你想要的元素的索引后，你可以对整个堆调用 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) 个元素会被交换。

回答于 2025-04-18 由 Python大师

分享举报

这是一个老问题，但如果将来有人看到这个并在寻找答案的话……

Python3中的heapq新实现包含了一些关于如何更新堆元素的有用说明，实际上是把它当作优先队列来使用。你可以创建一个包含元组的堆，Python会根据元组的顺序比较来评估优先级。因为在Python中，堆其实就是一个普通的列表，只是在上面使用了heapq这个接口，所以文档建议可以有一个额外的字典，将你的堆值映射到堆（列表）中的索引。

那么对于你最初的问题：

假设我在堆中有50个元素。我想把元素e3的值从val = 53改成val = 0。这个元素不是堆顶的元素。我也不想从堆中移除其他元素。我该如何进行这样的更新呢？

根据上面的逻辑，更新堆中元素的基本步骤是：

检查字典，以获取你想更新的元素的索引（在确认该元素在字典和对应的堆中后）
更新堆中的值
调用heapq.heapify(heap)，这个操作的时间复杂度是O(N)。另外，如果你知道你的更新只会让值增加或减少1，你也可以直接把你想更新的元素的位置和它上面或下面的元素交换。

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

回答于 2025-04-18 由 Python大师

分享举报

Python：更新heapq中的元素值

3 个回答

撰写回答