Implementing ArrayHeap

The questions in this section use this outline of ArrayHeap, a binary heap stored in an array in level order. It implements PriorityQueue<T>: add throws IllegalArgumentException if the item is null, and remove deletes the highest-priority element and throws NoSuchElementException if the heap is empty. The helpers below are already written.

public class ArrayHeap<T extends Comparable<T>> implements PriorityQueue<T> {
  private T[] heap;                  // the complete tree in level order, root at heap[0];
                                     // the constructors allocate it with length 10
  private int size;                  // heap[0] through heap[size - 1] are filled
  private Comparator<T> comparator;  // null means use natural ordering

  // 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(T a, T b) { ... }

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

  // The left child of the node at index i.
  private int leftChild(int i) { ... }

  // The right child of the node at index i.
  private int rightChild(int i) { ... }

  // Exchanges the elements at indices i and j.
  private void swap(int i, int j) { ... }

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

private void swim(int i) {
  while (i > 0 && compare(heap[i], heap[parent(i)]) < 0) {
    swap(i, parent(i));
    i = parent(i);
  }
}

private void sink(int i) {
  while (leftChild(i) < size) {
    int best = leftChild(i);
    int right = rightChild(i);
    if (right < size && compare(heap[right], heap[best]) < 0) {
      best = right;
    }
    if (compare(heap[best], heap[i]) >= 0) {
      break;
    }
    swap(i, best);
    i = best;
  }
}

@Override
public void add(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  if (size == heap.length) {
    grow();
  }
  heap[size] = item;
  size++;
  swim(size - 1);
}

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