Update changes an element’s priority while preserving the priority-queue invariant. A priority queue exposes update(element, newPriority); a heap supplies one concrete implementation. section 2.4
After locating the element, compare its old and new priorities. Move it upward when its priority improves, or downward when its priority worsens; stop when the parent and child relationships are valid again. section 2.6.5
Heap update procedure
Given oldValue and newPriority, find the element, replace its priority, then call bubbleUp when the new priority is better or pushDown when it is worse. An unchanged priority requires no repair. section 2.6.5
Listing 2.8 The update method
function update(oldValue, newPriority)
index ← pairs.find(oldValue) #1
if index ≥ 0 then #2
oldPriority ← pairs[index].priority
pairs[index] ← Pair(oldValue, newPriority)
if (newPriority < oldPriority) then #3
bubbleUp(pairs, index) #4
elsif (newPriority > oldPriority) then
pushDown(pairs, index) #5
The listing makes the search, replacement, and direction-specific heap repair explicit. section 2.6.5
The repair costs logarithmic time in a heap, but locating the element can take linear time. An index map or hash table reduces lookup to amortized constant time, making the complete operation amortized logarithmic. section 2.6.5 section 7.7.3
Treaps use rotations rather than simple swaps for the same upward or downward adjustment. In Dijkstra’s algorithm, update efficiency directly affects the algorithm’s total running time. section 3.3.6 section 14.4.3
