Problem: Cancel a Job

The queue always serves the highest-priority job first. Sometimes, though, a job has to leave the queue before it is served. For example, a user cancels a print job. To handle that, you need to take one specific job out of the queue, wherever it is, not just the one at the front.

The method sits inside the class, so it can use the heap array, the index map, and the private helpers:

public void remove(T item) {

}

The existing remove takes out the root. The hole is always at the top, so the last entry moves up into it and sinks. Here the hole can be anywhere. The index map makes finding the item easy: one lookup gives you its slot. The harder part is repairing the heap after the item is gone.

Suppose the queue holds six jobs:

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

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

Example 1:

remove("F") removes the job in the last slot. Nothing has to move to fill the hole: drop it from the array and the map, and the heap that remains is still valid.

Example 2:

remove("E") removes the job at slot 4, which is not the last slot. The last entry, F at priority 4, moves into the hole at slot 4. But F at priority 4 outranks its new parent B at slot 1, priority 5, so F has to swim up. The result:

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 obvious approach is to copy the root remove: drop the item, move the last entry into the gap, and sink it. But sinking F does nothing here, because slot 4 has no children. F would stay below its parent B even though it outranks B, and the heap would stay broken. If F had landed above a child that outranks it, it would have had to sink instead. So the filler does not always move in the same direction. After you drop the item and move the last entry into the gap, which way does the filler need to go, and how do you cover both cases without checking by hand each time?