# Update priority of existing item in a minmax heap

Say you have a double ended priority queue in the form of a minmax heap as described here.

What is the most efficient algorithm to update the priority of an existing item?

Assume that

1. I explicitly want to avoid deleting and re-inserting the item
2. The index of the existing item (pre-update) in the heap is known (so no linear search needed to find it)

My general thoughts so far: Let i be the index of the item to be updated.

First, update its actual priority value priority[i] = new priority, then ...

1. i=0 (root of the smallest min layer), or i=1 or i=2 (roots of the largest max layer), then update the value and sift down
2. If i is at a leaf position, then sift-up as usual

The interesting cases happen if neither of this is true of course, i.e. i is somewhere in the middle of the tree. And that's where I'm not quite sure about correctness.

I think the following should hold true:

1. If i is on a min layer, and the priority[i] < priority[grandparent_of[i]], then SiftUp(i)
2. If i is on a max layer, and priority[i] > priority[grandparent_of[i]], then SiftUp(i)

Even trickier..

1. If i is on a min layer, and priority[i] > priority[parent_of[i]], then...

• Swap priorities: (priority[i], priority[parent_of[i]] )= (priority[parent_of[i], priority[i]). Afterwards,
• SiftUp(parent_of[i]), then
• SiftDown(i)
2. Similarly, if i is on a max layer, and priority[i] < priority[parent_of[i]], then...

• Swap priorities: (priority[i], priority[parent_of[i]] )= (priority[parent_of[i], priority[i]). Afterwards,
• SiftUp(parent_of[i]), then
• SiftDown(i)
3. And if neither of these conditions are fulfilled, then.. I think the heap is still valid and nothing needs to be done, unless I missed a case!

I'm having a very hard time arguing about the correctness of anything after step 2 though, so I wonder if this is actually right.

My thinking behind the logic of step 5, for example, is:

• Since iis on a min-layer, and hence parent[i] is on a max-layer, the entire subtree of parent[i] must have values smaller than priority[parent[i]]. Since we're swapping priorioty[parent[i]] with some larger value, that invariant is definitely still satisfied.
• The entire subtree of i must have values smaller than priority[i]. We know that the value being swapped into slot i is larger than the value that was there before. Hence, this invariant is still satisfied too.
• Since we have replaced priority[parent[i]] with something larger, it's possible that after the swap, priority[parent[i]] > priority[grandparent_of[parent[i]]], hence we sift-up parent[i]
• Similarly, since we have replaced priority[i] with something larger, it's possible that priority[i] > priority[grandchild_of[i]], so we sift-down i

Is there any literature on how an update really looks like? Or does anyone smarter than me have any thoughts on correctness of my idea above?