The Adaptive Priority Queue

An adaptive priority queue lets an item’s priority change while the item waits in the queue. We build it from a binary heap and an index map that records the position of each item in the heap.

After reading this chapter, you should be able to:

  • Explain why an adaptive priority queue keeps each item separate from its priority, so that a waiting item’s priority can change
  • Specify the adaptive priority queue in Javadoc, with items that must be distinct and priorities that may repeat
  • Replace the binary heap’s scan for an item with an index map from each item to its slot
  • Maintain the index map’s invariant as the heap moves items, by updating the map in swap, add, and remove
  • Implement the IndexedArrayHeap, with changePriority using swim for a decrease-key and sink for an increase-key
  • Trace add, remove, and changePriority on the IndexedArrayHeap, showing the heap and the index map after each swap
  • Analyze the IndexedArrayHeap with a TreeMap index map, showing that the map updates in each swap make add, remove, and changePriority
  • Change a priority with Java’s PriorityQueue by adding the item again and skipping its old copy, and state the limits of that approach

You can download the accompanying code for this chapter: starter and solution.

Sections

  1. When a Priority Changes
  2. The changePriority Operation
  3. Adaptive Priority Queue Specification
  4. Finding an Item in a Heap
  5. An Index Map
  6. The IndexedArrayHeap Class
  7. Implementing add
  8. Implementing remove
  9. Implementing changePriority
  10. The Cost of the Index Map
  11. Java’s PriorityQueue