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