A Heap Built from Nodes

The tree chapter built binary trees from nodes, each with a value and a left and a right reference. A heap is a binary tree, so we start there.

Here is the class, with its fields and constructors:

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

  private Node<T> root;
  private int size;
  private Comparator<T> comparator;  // null means use natural ordering

  private static class Node<T> {
    T value;
    Node<T> left;
    Node<T> right;

    Node(T value) {
      this.value = value;
    }
  }

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

  // Orders the elements by the given comparator.
  public LinkedHeap(Comparator<T> comparator) {
    root = null;
    size = 0;
    this.comparator = comparator;
  }

  // ... the operations will go here
}

The two constructors are the two options the priority queue specification described: natural ordering, where the smallest element has the highest priority, or a Comparator<T>.

Several operations need to know which of two elements has the higher priority, so that decision goes in one helper:

// 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) {
  if (comparator != null) {
    return comparator.compare(a, b);
  }
  return a.compareTo(b);
}

If you pass a comparator that reverses the natural ordering, the heap becomes a max-heap. Nothing else in the code has to change.

size and peek

size reads the field:

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

The order property keeps the highest-priority element at the root, so peek reads the root’s value. It throws a NoSuchElementException if the heap is empty:

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

What add and remove need

The two operations that change the heap are harder. In the priority queue chapter, add puts the new element in the next open slot on the bottom level, then swims it up. remove moves the value of the last node into the root, deletes the last node, then sinks the root down.

Both raise problems when the heap is built from nodes.

• Where is the next open slot, and where is the last node? In the drawings, we could see them. In code, we only have root and size, and the slot is somewhere at the bottom of the tree.
• How does swim get back up? Swimming compares a node with its parent, and then with that parent’s parent. But a Node has only left and right, which point down.

sink does not have the second problem. It starts at the root and moves down through left and right, which is the direction the references point.