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

Question

使用最小/最大堆算法时,优先级可能会发生变化.处理此问题的一种方法是删除并插入元素以更新队列顺序.

对于使用数组实现的优先级队列,这可能是一个似乎可以避免的性能瓶颈,特别是对于优先级变化较小的情况.

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

是否有众所周知的最佳实践方法来更新min/max-heap中的元素？

---

背景信息:我不是二叉树专家,我继承了一些代码,这些代码在优先级队列中重新插入了元素.我为重新排序新元素的min-heap做了一个重新插入函数 - 这给了一个可测量的改进(删除和插入),但这似乎是其他人可能已经解决的更优雅的问题办法.

我可以链接到代码,如果它有所帮助,但宁愿不太关注实现细节 - 因为这个Q&A可能保持一般.

Answer 1

典型解决方案

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

替代方案

如果该方法不足够的,因此能够恢复最小堆不变在O(log n)的步骤,只要被改变的值的位置是已知的.

回想一下,min-sheaps是使用两个原语"siftup"和"siftdown"构建和维护的(虽然各种来源对于哪个来源有不同的意见,哪些是关闭的).其中一个将值推到树下,另一个将它们向上浮动.

案例1:价值增加

如果新值x1大于旧值x0,则只需要修复x下的树,因为parent(x) <= x0 < x1.只需将x与其两个子节点中较小的一个交换x,然后x大于其中一个子节点,就可以向下推x.

案例2:价值下降

如果新值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

Answer 2

发布自己问题的答案，因为它包含指向工作代码的链接。

这其实很简单。

通常，最小堆实现具有排序功能，请参见示例： BubbleUp/Down。

这些函数可以在修改后的元素上运行，具体取决于相对于当前值的变化。例如：

if new_value < old_value {
    heap_bubble_up(heap, node);
} else if new_value > old_value {
    heap_bubble_down(heap, node);
}

虽然操作的数量取决于值的分布，但与维护排序列表相比，这将是相等或更少的步骤。

一般来说，小的更改比删除+插入更有效。

请参阅工作代码和test，它实现了一个带有插入/删除/重新优先级的最小堆，无需初始查找（调用者存储不透明引用）。

即使只对所需元素重新排序，对于大堆来说也可能是许多操作。

如果这太低效，最小堆可能不太适合。

二叉树可能更好（例如红黑树），其中删除和插入的扩展性更好。

但是，我不确定 rb-trees 是否能够像 min-heap 那样就地重新排序。