35

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

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

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

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

背景信息：我不是二叉树专家，我继承了一些在优先级队列中重新插入元素时存在性能瓶颈的代码。我已经为重新排序新元素的最小堆创建了一个重新插入函数 - 这对（删除和插入）提供了可衡量的改进，但这似乎是其他人可能已经解决的问题更优雅方法。

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

4

2 回答 2

44

典型解决方案

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

替代解决方案

如果这种方法还不够，只要知道要更改的值的位置，就可以在 O(log n) 步骤中恢复最小堆不变量。

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

案例一：价值增加

如果新值x1大于旧值x0 ，则只需修复x下的树，因为parent(x) <= x0 < x1. 只需将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
于 2017-10-29T04:22:03.650 回答
6

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

这其实很简单。

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

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

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

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

一般而言，小的更改_much_ 比删除+插入更有效。

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

即使仅重新排序所需的元素也可能最终成为大型堆的许多操作。

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

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

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

于 2017-10-29T08:14:53.760 回答