The Cost of the Index Map

The map we are using is the TreeMap from the TreeMap chapter, built on an AVL tree, so each of its operations (get, put, remove, containsKey) costs $O(\log n)$ on a map of $n$ entries. Our map holds one entry per item in the queue, so here $n$ is the queue’s size, the same $n$ as the heap.

Take changePriority. It does one get to find the item, which is $O(\log n)$. Then it swims or sinks, which is at most $\log n$ swaps, one per level. Each swap now updates the map for the two items it moved, which is two put calls at $O(\log n)$ each. So the swaps cost $O({\log }^{2}n)$, the lookup is small next to that, and changePriority is $O({\log }^{2}n)$.

add and remove work out the same way. Each does a fixed number of map operations outside its swim or sink: a check and a put for add, and a swap (two puts) and a remove for remove. Then each does a swim or a sink, and that costs $O({\log }^{2}n)$ in map updates, the same as in changePriority. So remove is $O({\log }^{2}n)$ too. So is add, but its cost is amortized, because now and then it doubles the array, as ArrayHeap.add did in the binary heap chapter.

contains is cheaper, because it does no swaps. It is a single containsKey, so it is $O(\log n)$. And peek never touches the map, so it stays $O(1)$.

In the plain heap, add and remove are $O(\log n)$, so the index map adds a factor of $\log n$ to them.

There is a way to implement the index map with constant-time operations, using a hash table. We learn about hash tables in the next few chapters.