如何更新堆中的元素？ （优先级队列） [英] How to update elements within a heap? (priority queue)

问题描述

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

When using a min/max-heap algorithm, priorities may change. One way to handle this is to removal and insert the element to update the queue order.

对于使用数组实现的优先级队列，这可能是一个性能瓶颈，似乎可以避免，

For priority queues implemented using arrays, this can be a performance bottleneck that seems avoidable, especially for cases when the change to priority is small.

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

Even if this is not a standard operation for a priority queue, this is a custom implementation which can be modified for my needs.

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

Are there well known best-practice methods for updating elements in the min/max-heap?

背景信息：我不是二叉树专家，我继承了一些在优先级队列中重新插入元素的性能瓶颈的代码。我为min-heap做了一个重新插入功能，对新元素进行了重新排序-相对于（删除和插入）有了明显的改进，但是这似乎是其他人可能已经解决的问题。

如果可以帮助的话，我可以链接到代码，但不希望过多地关注实现细节-因为本问答集

推荐答案

典型解决方案

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

Typical Solution

The usual solution is to mark an element as invalid and insert a new element, then eliminate the invalid entries as they are popped-off.

如果该方法不能满足要求，只要更改值的位置，就可以恢复O（log n）步骤中的最小堆不变量。回想起。

If that approach doesn't suffice, it is possible restore the min-heap invariant in O(log n) steps as long as the location of the value being changed is known.

回想一下，最小堆是使用 siftup和 siftdown两个原语构建和维护的（尽管有多种消息来源对哪个上升和下降有不同的看法。其中一种将价值推向树下，另一种将价值推向树上。

Recall that min-heaps are built and maintained using two primitives, "siftup" and "siftdown" (though various sources have differing opinions on which is up and which is down). One of those pushes values down the tree and the other floats them upward.

如果新值 x1 大于旧值 x0 ，则仅需修复 x 下的树，因为 parent（x）< = x0< x1 。通过将 x 交换为两个子节点中较小的一个，而 x 大于一个子节点中的一个将 x 向下推到树上。

If the new value x1 is greater than the old value x0, then only the tree under x needs to be fixed because parent(x) <= x0 < x1. Just push x down the tree by swapping x with the smaller of its two children while x is bigger than one of its children.

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

If the new value x1 is less than the old value x, the tree below x needs no adjustment because x1 < x0 <= either_child(x). Instead, we just need to move upward, swapping x with its parent while x is less than its parent. Sibling nodes need not be considered because they are already greater than or equal to a parent which will potentially be replaced with a lower value.

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

No work is necessary. The existing invariants are unchanged.

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

Test 1,000,000 trials: Create a random heap. Alter a randomly selected value. Restore the heap condition. Verify that the result is a min-heap.

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

这篇关于如何更新堆中的元素？ （优先级队列）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！