Question
How to update elements within a heap? (priority queue)
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.