The IndexedArrayHeap Class

The IndexedArrayHeap is the binary heap with the index map added.

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

  private Entry<T, P>[] heap;     // the complete tree, stored in level order
  private Map<T, Integer> index;  // each item to the slot it occupies
  private int size;

  @SuppressWarnings("unchecked")
  public IndexedArrayHeap() {
    heap = (Entry<T, P>[]) new Entry[10];
    index = new TreeMap<>();
    size = 0;
  }

  // ... the operations will go here
}

The constructor creates an Entry[] and casts it, as ArrayMap did in the map chapter, because Entry<T, P> erases to Entry.

T is Comparable because the index map is a TreeMap, and a TreeMap needs comparable keys.

The size operation reads the field directly:

@Override
public int size() {
  return size;
}

compare from the binary heap chapter now compares two priorities:

private int compare(P a, P b) {
  return a.compareTo(b);
}

The rest of the binary heap code carries over: the index arithmetic (parent, leftChild, rightChild), grow (now creating an Entry array), and swim and sink (now passing the entries’ priorities to compare).

peek is the same as in the binary heap chapter. The only change is that it reads the item out of the entry:

@Override
public T peek() {
  if (size == 0) {
    throw new NoSuchElementException();
  }
  return heap[0].item;  // the highest-priority item is always at the root
}

contains uses the map:

@Override
public boolean contains(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  return index.containsKey(item);
}