Implementing changePriority

changePriority finds the item through the map, then overwrites its priority and swims or sinks the item to restore the heap:

@Override
public void changePriority(T item, P priority) {
  if (item == null || priority == null) {
    throw new IllegalArgumentException();
  }
  Integer i = index.get(item);  // where the item sits, or null if absent
  if (i == null) {
    throw new NoSuchElementException();
  }
  P old = heap[i].priority;
  heap[i].priority = priority;
  if (compare(priority, old) < 0) {
    swim(i);  // higher priority now: move up
  } else if (compare(priority, old) > 0) {
    sink(i);  // lower priority now: move down
  }
}

compare(priority, old) says which way the priority moved. If the new priority is smaller than the old one, the item should now be served sooner. It may now outrank its parent, so it may have to move up. Its children still do not outrank it, so it never needs to move down. The only fix it can need is to swim, which is the decrease-key from earlier. If the new priority is larger, the item should be served later, and the reverse is true: the item may now be outranked by a child and have to sink, but it still does not outrank its parent, so it never swims. That is the increase-key. If the priority did not change, there is nothing to do.

The changePriority(Dan, 1) we kept coming back to is a decrease-key. Start from the heap and index map of the earlier sections.

The map says Dan is at slot 3, so we go straight there and set his priority to 1:

heap
         ┌─────┬─────┬─────┬─────┬─────┐
 index   │   0 │   1 │   2 │   3 │   4 │
         ├─────┼─────┼─────┼─────┼─────┤
 item    │ Amy │ Bob │ Cal │░Dan░│ Eve │
         ├─────┼─────┼─────┼─────┼─────┤
 prio    │   1 │   2 │   4 │░  1░│   3 │
         └─────┴─────┴─────┴─────┴─────┘

index map
         ┌─────┬─────┬─────┬─────┬─────┐
 item    │ Amy │ Bob │ Cal │░Dan░│ Eve │
         ├─────┼─────┼─────┼─────┼─────┤
 index   │   0 │   1 │   2 │░  3░│   4 │
         └─────┴─────┴─────┴─────┴─────┘

The heap is now out of order: Dan outranks his parent Bob. This is a decrease-key, so the fix is to swim:

heap
         ┌─────┬─────┬─────┬─────┬─────┐
 index   │   0 │   1 │   2 │   3 │   4 │
         ├─────┼─────┼─────┼─────┼─────┤
 item    │ Amy │░Dan░│ Cal │░Bob░│ Eve │
         ├─────┼─────┼─────┼─────┼─────┤
 prio    │   1 │░  1░│   4 │░  2░│   3 │
         └─────┴─────┴─────┴─────┴─────┘

index map
         ┌─────┬─────┬─────┬─────┬─────┐
 item    │ Amy │░Bob░│ Cal │░Dan░│ Eve │
         ├─────┼─────┼─────┼─────┼─────┤
 index   │   0 │░  3░│   2 │░  1░│   4 │
         └─────┴─────┴─────┴─────┴─────┘

Dan stops at slot 1 because his priority ties with Amy’s, and swim moves an entry only while it outranks its parent.

Now an increase-key. Start again from the same heap, and say Amy’s condition improves, so we call changePriority(Amy, 6). The map says Amy is at slot 0, so we set her priority to 6 there:

heap
         ┌─────┬─────┬─────┬─────┬─────┐
 index   │   0 │   1 │   2 │   3 │   4 │
         ├─────┼─────┼─────┼─────┼─────┤
 item    │░Amy░│ Bob │ Cal │ Dan │ Eve │
         ├─────┼─────┼─────┼─────┼─────┤
 prio    │░  6░│   2 │   4 │   5 │   3 │
         └─────┴─────┴─────┴─────┴─────┘

index map
         ┌─────┬─────┬─────┬─────┬─────┐
 item    │░Amy░│ Bob │ Cal │ Dan │ Eve │
         ├─────┼─────┼─────┼─────┼─────┤
 index   │░  0░│   1 │   2 │   3 │   4 │
         └─────┴─────┴─────┴─────┴─────┘

Both of Amy’s children now outrank her: Bob at 2 and Cal at 4. This is an increase-key, so the fix is to sink. Amy swaps with the more urgent child, Bob:

heap
         ┌─────┬─────┬─────┬─────┬─────┐
 index   │   0 │   1 │   2 │   3 │   4 │
         ├─────┼─────┼─────┼─────┼─────┤
 item    │░Bob░│░Amy░│ Cal │ Dan │ Eve │
         ├─────┼─────┼─────┼─────┼─────┤
 prio    │░  2░│░  6░│   4 │   5 │   3 │
         └─────┴─────┴─────┴─────┴─────┘

index map
         ┌─────┬─────┬─────┬─────┬─────┐
 item    │░Amy░│░Bob░│ Cal │ Dan │ Eve │
         ├─────┼─────┼─────┼─────┼─────┤
 index   │░  1░│░  0░│   2 │   3 │   4 │
         └─────┴─────┴─────┴─────┴─────┘

At slot 1, Amy’s children are Dan at 5 and Eve at 3. Eve is the more urgent, and her 3 outranks Amy’s 6, so they swap:

heap
         ┌─────┬─────┬─────┬─────┬─────┐
 index   │   0 │   1 │   2 │   3 │   4 │
         ├─────┼─────┼─────┼─────┼─────┤
 item    │ Bob │░Eve░│ Cal │ Dan │░Amy░│
         ├─────┼─────┼─────┼─────┼─────┤
 prio    │   2 │░  3░│   4 │   5 │░  6░│
         └─────┴─────┴─────┴─────┴─────┘

index map
         ┌─────┬─────┬─────┬─────┬─────┐
 item    │░Amy░│ Bob │ Cal │ Dan │░Eve░│
         ├─────┼─────┼─────┼─────┼─────┤
 index   │░  4░│   0 │   2 │   3 │░  1░│
         └─────┴─────┴─────┴─────┴─────┘

Amy is now at slot 4, a leaf, so the sink stops.