使用最小/最大堆算法时，优先级可能会发生变化。一种解决方法是删除并插入元素以更新队列顺序。
对于使用数组实现的优先级队列，这可能是一个可以避免的性能瓶颈，尤其是对于优先级变化很小的情况。
即使这不是优先级队列的标准操作，这也是一个自定义实现，可以根据我的需要进行修改。
是否有众所周知的最佳实践方法来更新最小/最大堆中的元素？
背景信息：我不是二进制树的专家，我继承了一些代码，该代码在优先级队列中重新插入元素时存在性能瓶颈。 我为min- heap做了一个重新插入功能，对新元素进行了重新排序-相对于（删除和插入）有了可衡量的改进，但是这似乎是其他人可以更优雅地解决的问题方式。
如果有帮助，我可以链接到代码，但不想过多地关注实现细节-因为此问与答可能可以保持一般性。
通常的解决方案是将元素标记为无效并插入新元素，然后在弹出无效条目时消除它们。
如果该方法不能满足要求， 则只要知道要更改的值的位置 ， 就可以按O（log n）步骤还原最小堆不变式 。
回想一下，最小堆是使用两个基本变量“ siftup”和“ siftdown”构建和维护的（尽管各种来源对哪个向上和哪个向下有不同的看法）。其中一个将值向下推到树上，另一个将其向上浮动。
如果新值 x1 大于旧值 x0 ，则仅需要固定 x 下的树，因为parent(x) <= x0 < x1。只需 按下 X 在树中通过交换 X 与它的两个孩子的小，而 X 是其子大于1。
parent(x) <= x0 < x1
如果新值 x1 小于旧值 x ，则 x 下方的树不需要调整，因为x1 < x0 <= either_child(x)。相反，我们只需要 向上移动，即可 在 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
