public int extract() {
            if (bottom == 0) {
                throw new IllegalStateException("Called extract() on empty heap");
            }
            int idx = 1;
            final int top = heap[idx];
            heap[idx] = heap[bottom--];
            // percolate down
            for (; idx < bottom;) {
                final int leftIdx = idx * 2;
                if (leftIdx > bottom) {
                    // no children, heap resolved.
                    break;
                }
                final int leftValue = heap[leftIdx];
                final int rightIdx = leftIdx + 1;
                final int currVal = heap[idx];
                // guard against rightIdx
                if ((rightIdx > bottom || ordering.compare(leftValue, heap[rightIdx]) >= 0)) {
                    if (ordering.compare(currVal, leftValue) < 0) {
                        heap[leftIdx] = currVal;
                        heap[idx] = leftValue;
                        idx = leftIdx;
                    } else {
                        // heap resolved
                        break;
                    }
                } else if (ordering.compare(currVal, heap[rightIdx]) < 0) {
                    heap[idx] = heap[rightIdx];
                    heap[rightIdx] = currVal;
                    idx = rightIdx;
                } else {
                    // heap resolved
                    break;
                }
            }
            return top;
        }