Finding an Item with an Index Map

The questions in this section use a binary heap that stores an adaptive priority queue in an array, in level order. The highest-priority entry is at the root, at index 0. Each entry holds an item and its priority, an integer. The queue serves the smallest priority first, and the items are distinct. add places the new entry in the next open slot and swims it up. remove moves the last entry into the root and sinks it down.

Solution

It is , a linear scan of the array. The array is not sorted by item. The order property only keeps each entry’s priority no larger than its children’s priorities, so the array is not sorted by priority either. It cannot be binary-searched.

Solution

The keys are the items in the queue, and each value is the index of the slot where that item sits. changePriority gets the item’s slot from the map in one lookup, overwrites the priority stored there, and then swims or sinks the entry.

Solution
  • swap must record the new slots of the two items it exchanged. swim and sink move entries only through swap, so they need no map code of their own.
  • add must record the new item at the slot where it is placed, before it swims.
  • remove must drop the removed root’s item from the map and record that the last entry now sits at index 0, before it sinks.