How to update elements within a heap? (priority qu

问题:

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.

回答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

回答2:

Posting answer to own question since it includes links to working code.

---

This is in fact quite simple.

Typically a min-heap implementation has functions for ordering, see example: BubbleUp/Down.

These functions can run on the modified element, depending on the change relative to the current value. eg:

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

While the number of operations depends on the distribution of values, this will be equal or fewer steps then maintaining a sorted list.

In general, small changes are _much_ more efficient than a remove+insert.

See working code, and test, which implements a min-heap with insert/remove/re-prioritize, without an initial lookup (the caller stores an opaque reference).

---

Even re-ordering only the required elements may end up being many operations for a large heap.

If this is too inefficient, a minimum heap may not a a good fit.

A binary-tree might be better (red-black tree for example), where removal and insertion scale better.

However I'm not sure about an rb-trees ability to re-order in-place, as a min-heap can do.