如何更新堆中的元素？（优先级队列）

  • Z时代
  • 2024-01-10
  • 分类：问答

使用最小/最大堆算法时，优先级可能会发生变化。一种解决方法是删除并插入元素以更新队列顺序。

对于使用数组实现的优先级队列，这可能是一个可以避免的性能瓶颈，尤其是对于优先级变化很小的情况。

即使这不是优先级队列的标准操作，这也是一个自定义实现，可以根据我的需要进行修改。

是否有众所周知的最佳实践方法来更新最小/最大堆中的元素？

背景信息：我不是二进制树的专家，我继承了一些代码，该代码在优先级队列中重新插入元素时存在性能瓶颈。 我为min-

heap做了一个重新插入功能，对新元素进行了重新排序-相对于（删除和插入）有了可衡量的改进，但是这似乎是其他人可以更优雅地解决的问题方式。

如果有帮助，我可以链接到代码，但不想过多地关注实现细节-因为此问与答可能可以保持一般性。

回答：

回答：

通常的解决方案是将元素标记为无效并插入新元素，然后在弹出无效条目时消除它们。

回答：

如果该方法不能满足要求， ， 。

回想一下，最小堆是使用两个基本变量“ siftup”和“

siftdown”构建和维护的（尽管各种来源对哪个向上和哪个向下有不同的看法）。其中一个将值向下推到树上，另一个将其向上浮动。

回答：

如果新值 x1 大于旧值 x0 ，则仅需要固定 x 下的树，因为parent(x) <= x0 < x1。只需 。

回答：

如果新值 x1 小于旧值 x ，则 x 下方的树不需要调整，因为x1 < x0 <= either_child(x)。相反，我们只需要

。

不需要考虑同级节点，因为它们已经大于或等于父级，而父级可能会被较低的值替换。

回答：

无需任何工作。现有的不变量不变。

回答：

测试1,000,000次试验：创建一个随机堆。更改随机选择的值。恢复堆条件。验证结果是最小堆。

from heapq import _siftup, _siftdown, heapify
from random import random, randrange, choice
def is_minheap(arr):
    return all(arr[i] >= arr[(i-1)//2] for i in range(1, len(arr)))
n = 40
trials = 1_000_000
for _ in range(trials):
    # Create a random heap
    data = [random() for i in range(n)]
    heapify(data)
    # Randomly alter a heap element
    i = randrange(n)
    x0 = data[i]
    x1 = data[i] = choice(data)
    # Restore the heap
    if x1 > x0:                 # value is increased
        _siftup(data, i)
    elif x1 < x0:               # value is decreased
        _siftdown(data, 0, i)
    # Verify the results
    assert is_minheap(data), direction

以上是 如何更新堆中的元素？（优先级队列） 的全部内容， 来源链接： utcz.com/qa/431913.html

回到顶部