Solution: Move the Last Entry into the Gap

Finding the item is a map lookup, the same one changePriority and contains use. For the repair, the plan is the one the root remove uses: move the last entry into the gap so the tree stays complete, then move that entry until the heap order holds again.

The difference from the root case is which way that entry may need to move. When the root leaves, the entry that fills the gap is at the top, so it can only be too low and needs to sink. When a middle item leaves, the entry that fills the gap can be too high or too low, depending on how its priority compares with the parent and children of that slot.

The fix is to call both:

public void remove(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  Integer i = index.get(item);  // where the item sits, or null if absent
  if (i == null) {
    throw new NoSuchElementException();
  }
  index.remove(item);        // the item is leaving
  heap[i] = heap[size - 1];  // move the last entry into the gap
  heap[size - 1] = null;     // clear the vacated slot
  size--;
  if (i < size) {            // the gap was not the last slot
    index.put(heap[i].item, i);  // the moved item now sits at i
    sink(i);  // it may be too low...
    swim(i);  // ...or too high; at most one of these moves it
  }
}

Calling both sink and swim looks like it might move the filler twice, but at most one of them moves it. Before the removal the heap was valid, so the parent of slot i was at least as urgent as the children of slot i. If the filler outranks that parent, it also outranks those children, so sink does nothing and swim moves the filler up. If instead a child outranks the filler, the filler cannot outrank the parent, so sink moves it down. The entry that sink brings up into slot i was one of those children, so it does not outrank the parent either, and swim does nothing.

When the item is already in the last slot, as in Example 1, there is no gap. The method moves the last entry into its own slot and clears it, and after size--, i equals size. The if is skipped.

Let’s trace remove("E") on the six-job queue from the problem. The map says E is at slot 4. After the removal and the move, F sits in slot 4 and the map records F -> 4:

heap
         ┌───┬───┬───┬───┬───┐
 index   │ 0 │ 1 │ 2 │ 3 │ 4 │
         ├───┼───┼───┼───┼───┤
 item    │ A │ B │ C │ D │░F░│
         ├───┼───┼───┼───┼───┤
 prio    │ 2 │ 5 │ 3 │ 8 │░4░│
         └───┴───┴───┴───┴───┘

index map
         ┌───┬───┬───┬───┬───┐
 item    │ A │ B │ C │ D │░F░│
         ├───┼───┼───┼───┼───┤
 index   │ 0 │ 1 │ 2 │ 3 │░4░│
         └───┴───┴───┴───┴───┘

Now we restore from slot 4. sink(4) finds no children there, so it does nothing. swim(4) compares F at priority 4 with its parent B at slot 1, priority 5. F outranks B, so they swap: F to slot 1, B to slot 4. F’s new parent is A at priority 2, which still outranks it, so the swim stops:

heap
         ┌───┬───┬───┬───┬───┐
 index   │ 0 │ 1 │ 2 │ 3 │ 4 │
         ├───┼───┼───┼───┼───┤
 item    │ A │░F░│ C │ D │░B░│
         ├───┼───┼───┼───┼───┤
 prio    │ 2 │░4░│ 3 │ 8 │░5░│
         └───┴───┴───┴───┴───┘

index map
         ┌───┬───┬───┬───┬───┐
 item    │ A │░B░│ C │ D │░F░│
         ├───┼───┼───┼───┼───┤
 index   │ 0 │░4░│ 2 │ 3 │░1░│
         └───┴───┴───┴───┴───┘

The lookup is one map operation. The repair is a sink and a swim, which together make $O (lo g n)$ swaps, and each swap updates the map. With the TreeMap, that comes to $O (lo g^{2} n)$ , the same as the chapter’s other operations that move entries. With a constant-time map, it would be $O (lo g n)$ .