Tracing the IndexedArrayHeap

IndexedArrayHeap stores a binary heap in an array, in level order, with the root at index 0. Each slot holds an item and its priority, and the queue serves the smallest priority first. The children of slot i are at $2i+1$ and $2i+2$. An index map records the slot each item occupies. Every swap updates the map for both items it moves. A swim swaps an entry with its parent while the entry outranks the parent. A sink swaps an entry with its higher-priority child while that child outranks it.

• add places the new entry in the next open slot, records that slot in the map, and swims the entry up.
• remove drops the root’s item from the map, moves the last entry into the root, records it at 0, and sinks it down.
• changePriority looks the item’s slot up in the map and overwrites its priority there. It swims the entry if the new priority is smaller than the old one and sinks it if the new priority is larger.

Write the heap as its entries in slot order, such as [Ann:15, Bea:45], and the map as {Ann=0, Bea=1}.

add(Kim, 50)    no swap
  heap  [Kim:50]
  map   {Kim=0}

add(Lee, 80)    no swap
  heap  [Kim:50, Lee:80]
  map   {Kim=0, Lee=1}

add(Max, 30)    Max swaps with Kim
  heap  [Max:30, Lee:80, Kim:50]
  map   {Kim=2, Lee=1, Max=0}

add(Ned, 60)    Ned swaps with Lee
  heap  [Max:30, Ned:60, Kim:50, Lee:80]
  map   {Kim=2, Lee=3, Max=0, Ned=1}

changePriority(Lee, 20)    Lee swims: swaps with Ned, then with Max
  heap  [Lee:20, Max:30, Kim:50, Ned:60]
  map   {Kim=2, Lee=0, Max=1, Ned=3}

changePriority(Max, 90)    Max sinks: swaps with Ned
  heap  [Lee:20, Ned:60, Kim:50, Max:90]
  map   {Kim=2, Lee=0, Max=3, Ned=1}

remove()        Lee leaves, Max moves to the root and swaps with Kim
  heap  [Kim:50, Ned:60, Max:90]
  map   {Kim=0, Max=2, Ned=1}

add(Ott, 40)    Ott swaps with Ned, then with Kim
  heap  [Ott:40, Kim:50, Max:90, Ned:60]
  map   {Kim=1, Max=2, Ned=3, Ott=0}