remove in Code

remove moves the value of the last node into the root, deletes the last node, and sinks the root down. Here is the public method:

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

A heap with one node is a special case: the root is also the last node, so there is no other node to move into the root. remove empties the tree.

Otherwise, removeLast detaches the last node, at position size, and returns its value.

Detaching the last node

To detach a node, we change a reference in its parent, so we have to reach the parent. Every digit of pathTo(size) except the last one leads down to the parent. The last digit says which child of the parent is the last node.

// Detaches the node at the end of path and returns its value.
// Pre: path has at least one step.
private T removeLast(String path) {
  Node<T> parent = root;
  for (int i = 0; i < path.length() - 1; i++) {
    if (path.charAt(i) == '0') {
      parent = parent.left;
    } else {
      parent = parent.right;
    }
  }
  T value;
  if (path.charAt(path.length() - 1) == '0') {
    value = parent.left.value;
    parent.left = null;
  } else {
    value = parent.right.value;
    parent.right = null;
  }
  return value;
}

Unlike add, this traversal is a loop, not a recursion. add has to come back up the path so it can swim the new value up. Here nothing happens on the way back, because sink starts at the root, so a loop is enough.

The precondition holds because remove only calls removeLast when the heap has at least two nodes, and the path to position 2 or higher has at least one digit. For example, with two nodes, the path to position 2 is 0. The loop runs zero times, parent stays at the root, and the root’s left child is detached.

sink

Here is sink:

// Moves the value in node down until no child outranks it.
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);
  }
}

The tree is complete, so a node with no left child has no right child either. That node is a leaf, and there is nowhere to sink to.

As in the priority queue chapter, we swap with the higher-priority child, so the value that moves up outranks the other child too.

sink follows one path down, and nothing happens on the way back, so it could be a loop, like removeLast. I wrote it as a recursion to match the other tree methods. The recursive call is the last thing it does.

The cost

The loop in removeLast follows the digits of the path, so detaching the last node is $O (lo g n)$ . sink goes down at most one level per call, so it makes at most about $lo g n$ calls, each doing a constant amount of work. So remove is $O (lo g n)$ .