Implementing remove

remove takes out the highest-priority item, the root. It swaps the root with the last entry, drops the root item, and sinks the entry that moved into the root. swap already records the new slots of both entries, so the only map change remove makes itself is to drop the item that leaves.

@Override
public void remove() {
  if (size == 0) {
    throw new NoSuchElementException();
  }
  swap(0, size - 1);                  // the root item moves to the last slot
  index.remove(heap[size - 1].item);  // the root item is leaving
  heap[size - 1] = null;              // clear the vacated slot
  size--;
  sink(0);
}

If the queue held only one item, the swap exchanges slot 0 with itself, and size is now 0. The root has no children, so sink stops right away, and the queue is empty.

Let’s trace a remove. Start from the heap at the end of the add trace in the previous section, where Fox swam to the root:

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

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

Call remove. The swap exchanges Fox and Cal, and updates both entries in the map:

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

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

Fox leaves the map, and its slot is cleared:

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

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

Cal sinks past Amy. The heap again holds the five patients it held before Fox was added, and the map records the slot of every item:

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

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