Implementing the IndexedArrayHeap

The questions in this section use this outline of IndexedArrayHeap, a binary heap stored in an array in level order, with an index map from each item to the slot it occupies. The queue serves the smallest priority first, and the items are distinct. It implements AdaptivePriorityQueue<T, P> with this contract:

• add(item, priority) throws IllegalArgumentException if the item or the priority is null, or if the item is already in the queue.
• remove() deletes the highest-priority item and throws NoSuchElementException if the queue is empty.
• changePriority(item, priority) gives the item a new priority. It throws IllegalArgumentException if the item or the priority is null, and NoSuchElementException if the item is not in the queue.

The index map is a Map<T, Integer> with these operations: put(key, value) adds the key or replaces its value, get(key) returns the value or null if the key is absent, remove(key) deletes the key, and containsKey(key) reports whether the key is present. The constructor sets index to a TreeMap, and T is Comparable because of that. The helpers below are already written.

public class IndexedArrayHeap<T extends Comparable<T>, P extends Comparable<P>>
    implements AdaptivePriorityQueue<T, P> {

  // An item together with its priority.
  private static final class Entry<T, P> {
    T item;
    P priority;

    Entry(T item, P priority) { ... }
  }

  private Entry<T, P>[] heap;     // the complete tree in level order, root at heap[0]
  private Map<T, Integer> index;  // each item to the slot it occupies
  private int size;               // heap[0] through heap[size - 1] are filled

  // Returns a negative number if a has higher priority than b, zero if they
  // tie, and a positive number if a has lower priority.
  private int compare(Entry<T, P> a, Entry<T, P> b) { ... }

  // The parent, left child, and right child of the node at index i.
  private int parent(int i) { ... }
  private int leftChild(int i) { ... }
  private int rightChild(int i) { ... }

  // Moves the entry at index i up until it does not outrank its parent.
  // Moves entries only by calling swap.
  private void swim(int i) { ... }

  // Moves the entry at index i down until no child outranks it.
  // Moves entries only by calling swap.
  private void sink(int i) { ... }

  // Replaces heap with an array of twice the length, holding the same entries.
  private void grow() { ... }
}

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);
  index.put(heap[j].item, j);
}

@Override
public void add(T item, P priority) {
  if (item == null || priority == null || index.containsKey(item)) {
    throw new IllegalArgumentException();
  }
  if (size == heap.length) {
    grow();
  }
  heap[size] = new Entry<>(item, priority);
  index.put(item, size);
  size++;
  swim(size - 1);
}

@Override
public void remove() {
  if (size == 0) {
    throw new NoSuchElementException();
  }
  index.remove(heap[0].item);
  heap[0] = heap[size - 1];
  heap[size - 1] = null;
  size--;
  if (size > 0) {
    index.put(heap[0].item, 0);
    sink(0);
  }
}

@Override
public void changePriority(T item, P priority) {
  if (item == null || priority == null) {
    throw new IllegalArgumentException();
  }
  Integer i = index.get(item);
  if (i == null) {
    throw new NoSuchElementException();
  }
  P old = heap[i].priority;
  heap[i].priority = priority;
  if (priority.compareTo(old) < 0) {
    swim(i);
  } else if (priority.compareTo(old) > 0) {
    sink(i);
  }
}