Implementing add

add puts a new item in and swims it up, as before. It first rejects a null item, a null priority, or an item that is already present, as the specification requires.

@Override
public void add(T item, P priority) {
  if (item == null || priority == null || index.containsKey(item)) {
    throw new IllegalArgumentException();
  }
  if (size == heap.length) {
    grow();
  }
  heap[size] = new Entry<>(item, priority);  // the next open slot
  index.put(item, size);                     // record where it sits
  size++;
  swim(size - 1);
}

We record the slot before swimming, so the map holds the item even if it never moves. If it does move, each swap on the way up updates the map, so wherever the item ends up, the map already points there.

To see this on a small heap, start with Amy 1, Bob 2, Cal 4, Dan 5, Eve 3:

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 │
         └─────┴─────┴─────┴─────┴─────┘

Call add("Fox", 0). The new entry goes at the end, in slot 5, and the map records that slot:

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

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

Fox has the smallest priority, so it swims up. Its first swap exchanges it with Cal, and the swap updates both entries in the map:

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

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

One more swap exchanges Fox with Amy. Fox is now at the root, and add is done:

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░│
         └─────┴─────┴─────┴─────┴─────┴─────┘