swim and sink in an Array

With the index helpers and swap in place, swim and sink move an element up or down the array.

swim

swim uses parent and swap:

// Moves the element at index i up until it does not outrank its parent.
private void swim(int i) {
  while (i > 0 && compare(heap[i], heap[parent(i)]) < 0) {
    swap(i, parent(i));
    i = parent(i);
  }
}

In LinkedHeap, swim used recursion, because a node had no way back to its parent. The calls waiting on the call stack held the path, and each one did a swim step as it returned. Here parent(i) computes the parent’s index, so nothing has to remember the path. A loop moves up the same path with i = parent(i).

The loop stops at the first parent that the element does not outrank. The recursion checked every ancestor on the path, even after the element had stopped moving up, because every waiting call runs its swimStep when it returns.

sink

sink does what it did in LinkedHeap. The null checks become bounds checks: a child exists only if its index is less than size.

// Moves the element at index i down until no child outranks it.
private void sink(int i) {
  while (leftChild(i) < size) {  // stop at a leaf
    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;  // no child outranks the element
    }
    swap(i, best);
    i = best;
  }
}

The loop runs while the node has a left child (leftChild(i) < size), since a node with no left child is a leaf. The right child is read only if it exists (right < size).

LinkedHeap’s sink was a recursion that called itself once, on the child it swapped with, as its last step. A recursion like that converts directly to a loop: the recursive call becomes i = best, and the base cases become the conditions that end the loop.