1
$\begingroup$

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?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.