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.
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.
To update priority in Priority Queue, get the index of the element that you want to update the priority of and assign a new key to the element. After updating the priority of an element, we need to heapify the heap to maintain the heap data structure.
Priority Queue is an extension of the queue with the following properties: Every item has a priority associated with it. An element with high priority is dequeued before an element with low priority.
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.
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.
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.
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.
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
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With