algorithm - How to update elements within a heap? (priority queue)

Question

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?

---

Background Info: I'm no expert in binary-trees, I inherited some code that has a performance bottleneck re-inserting elements in a priority queue. I've made a re-insertion function for the min-heap that re-orders the new element - which gives a measurable improvement over (remove & insert), however this seems the kind of problem that others may have solved in a more elegant way.

I could link to the code if it helps but would rather not focus too much on implementation details - since this Q&A can probably be kept general.

Answer 1

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.

Alternative Solution

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.

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.

Case 1: Value is increased

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.

Case 2: Value is decreased

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.

Case 3: Value is unchanged

No work is necessary. The existing invariants are unchanged.

Working code in Python

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