An Index Map

Here is one way to solve the problem of finding an item in a heap efficiently.

Keep a second structure beside the heap: a map that records, for each item, the index where it currently sits. A map looks a value up by its key instead of by position. Here the key is the item and the associated value is its index in the heap array. We will call this the index map.

Here is the heap from the previous example:

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

And here is the index map for the heap above:

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

Now changePriority(Dan, 1) asks the index map where Dan is, and the map answers 3 in one lookup. A map lookup has its own cost. From earlier chapters, you know it is $O (lo g n)$ when the map is a balanced search tree.

contains(Dan) is one lookup too: it asks the index map whether it has the key Dan.

Keeping the Map in Sync

The index map is only useful while its indices are correct. In a heap, items move around frequently as we add and remove elements, so the map has to be updated every time the heap changes. For example, when we swap two items in the heap, the map must reflect their new positions.

private void swap(int i, int j) {
  Entry<T, P> temp = heap[i];
  heap[i] = heap[j];
  heap[j] = temp;
  index.put(heap[i].item, i);  // the item now at i sits at i
  index.put(heap[j].item, j);  // the item now at j sits at j
}

This is the index map invariant: every item maps to the slot it occupies, so the map and the array always agree.

Swim and sink operations move items only by calling swap. They never write to the array themselves. So once swap maintains the invariant, swim and sink maintain it too, and we do not need to change them.