The ArrayHeap Class and Its Helpers

ArrayHeap implements the same PriorityQueue interface as LinkedHeap. Only the representation is new. Here is the class, with its fields and constructors:

public class ArrayHeap<T extends Comparable<T>> implements PriorityQueue<T> {

  private T[] heap;                  // the complete tree, stored in level order
  private int size;
  private Comparator<T> comparator;  // null means use natural ordering

  // Orders the elements by their natural ordering.
  public ArrayHeap() {
    this(null); // calls the other constructor with a null comparator
  }

  // Orders the elements by the given comparator.
  @SuppressWarnings("unchecked")
  public ArrayHeap(Comparator<T> comparator) {
    heap = (T[]) new Comparable[10];
    size = 0;
    this.comparator = comparator;
  }

  // ... the operations will go here
}

The heap array holds the tree in level order, as in the earlier section “A Heap in an Array”, with the root at heap[0]. The size field records how many slots are filled, so the heap occupies heap[0] through heap[size - 1]. The array starts with room for 10 elements and grows when it fills.

The elements have to be comparable, so the array is created as a Comparable[] and cast to T[], the same cast the sorted array chapter used for its backing array.

The comparator field and the compare helper are the same as in LinkedHeap, and the constructors set comparator the same way. size reads the field, as before:

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

Index helpers

The index arithmetic goes into three one-line methods:

// The parent of the node at index i. Pre: i > 0.
private int parent(int i) {
  return (i - 1) / 2;
}

// The left child of the node at index i.
private int leftChild(int i) {
  return 2 * i + 1;
}

// The right child of the node at index i.
private int rightChild(int i) {
  return 2 * i + 2;
}

Swimming and sinking each swap two slots, so that gets its own helper:

// Exchanges the elements at indices i and j.
private void swap(int i, int j) {
  T temp = heap[i];
  heap[i] = heap[j];
  heap[j] = temp;
}

This is the array form of swapValues in LinkedHeap.