algorithm - 如何更新堆中的元素？ (优先队列)

Question

当使用最小/最大堆算法时，优先级可能会改变。处理此问题的一种方法是删除和插入元素以更新队列顺序。

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

Even if this is not a standard operation for a priority queue ，这是一个自定义实现，可以根据我的需要进行修改。

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

---

背景信息:我不是二叉树方面的专家，我继承了一些在优先级队列中重新插入元素时存在性能瓶颈的代码。我为重新排序新元素的最小堆做了一个重新插入函数——这比(删除和插入)有了可衡量的改进，但是这似乎是其他人可能已经以更优雅的方式解决的问题方式。

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

Answer 1

典型方案

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

替代方案

如果该方法不够用，可以在 O(log n) 步内恢复最小堆不变性，只要知道要更改的值的位置。

回想一下，最小堆是使用两个原语“siftup”和“siftdown”构建和维护的(尽管各种来源对哪个是向上哪个是向下有不同的看法)。其中一个将值向下推到树上，另一个将它们向上 float 。

案例一:值(value)增加

如果新值x1大于旧值x0，那么只需要修复x下的树，因为parent(x) <= x0 < x1。只需将 x 与其两个子节点中较小的一个进行交换，将 x 推下树，而 x 比其中一个子节点大.

案例2:值(value)下降

如果新值 x1 小于旧值 x，则 x 下面的树不需要调整，因为 x1 < x0 <= either_child(x) 。相反，我们只需要向上移动，将 x 与其父元素交换，同时 x 小于其父元素。不需要考虑兄弟节点，因为它们已经大于或等于父节点，父节点可能会被替换为较低的值。

情况3:值不变

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

Python 中的工作代码

测试 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