Priority queue order

[hopesfall]

So in the textbook I'm reading about priority queues and one of the side questions that stumped me is this:

Suppose that after you have placed several items into a priority queue, you need to adjust one of their priority values. For example, a particular task in a priority queue of tasks could become either more or less urgent. How can you adjust a heap if a single priority value changes?

[Duthomhas]

Consider how you store things in a priority queue. For this example, consider priority to be greatest at 1 and least at N.

A=1
B=2
C=3

The queue then is a list of the form (A₁ A₂ B₁ B₂ B₃ C₁), where the list is ordered highest to lowest priority.

What would happen to the list if B's priority was changed to 5?

[JLBorges]

> How can you adjust a heap if a single priority value changes?

Recall that a heap is a binary tree with
a. the 'shape property' - it is a complete binary tree with each level filled from left to right
b. the 'value property' - the priority of a parent node can't be greater than the priority of the child nodes.

So, if you increase the priority of a node, do a 'sift up' from that node to the root - check if its priority is greater than that of its its parent and if so swap the two; else break ; repeat in a loop.

If the priority of a node is decreased, do a 'sift down' - check if its priority is lower than that of either of its children, and if so swap it with the child with the higher priority; else break ; repeat in a loop.

Worst case O( log N ) time.