Implementing the Linked Heap

The questions in this section use this outline of LinkedHeap, a binary heap built from nodes. 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. Positions are numbered in level order, starting from 1 at the root.

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;
    }
  }

  // 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 directions from the root to the node at position, one character per
  // step: '0' for left and '1' for right. The root is position 1.
  private String pathTo(int position) { ... }

  // Exchanges the values of nodes a and b. The nodes stay where they are.
  private void swapValues(Node<T> a, Node<T> b) { ... }

  // Detaches the node at the end of path and returns its value.
  // Pre: path has at least one step.
  private T removeLast(String path) { ... }
}

Exercise

Write the public add and its recursive helper. Nodes have no parent reference, and you may not use a separate stack: each call of the helper swims the new value up one step as it returns.

@Override
public void add(T item) {

}

// Attaches a new node holding item at the end of path, below node, and swims
// it up as the calls return. index is the next step of path to take.
// Returns the root of the subtree.
private Node<T> add(Node<T> node, T item, String path, int index) {

}

Solution

@Override
public void add(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  size++;
  root = add(root, item, pathTo(size), 0);
}

private Node<T> add(Node<T> node, T item, String path, int index) {
  if (index == path.length()) {
    return new Node<>(item);  // the open slot
  }
  Node<T> child;
  if (path.charAt(index) == '0') {
    node.left = add(node.left, item, path, index + 1);
    child = node.left;
  } else {
    node.right = add(node.right, item, path, index + 1);
    child = node.right;
  }
  if (compare(child.value, node.value) < 0) {
    swapValues(node, child);
  }
  return node;
}

Solution

private void sink(Node<T> node) {
  Node<T> best = node.left;
  if (best == null) {
    return;  // a leaf
  }
  if (node.right != null && compare(node.right.value, best.value) < 0) {
    best = node.right;
  }
  if (compare(best.value, node.value) < 0) {
    swapValues(node, best);
    sink(best);
  }
}

Solution

@Override
public void remove() {
  if (size == 0) {
    throw new NoSuchElementException();
  }
  if (size == 1) {
    root = null;
    size = 0;
    return;
  }
  root.value = removeLast(pathTo(size));
  size--;
  sink(root);
}

Solution

add is $O (lo g n)$ . The helper makes one call per step of a path about $lo g n$ long, and each call does one comparison and at most one swap.
remove is $O (lo g n)$ . removeLast follows a path about $lo g n$ long, and sink moves down at most one level per call, with constant work per call.