힙 정렬 (Heap Sort)

/**
 * k 노드의 위치를 swim 방식으로 복구한다.
 *
 * @param k 정렬 상태를 위반하는 노드의 배열 인덱스
 */
private void swim(int k) {
  int rootNode = 1;
  while ( k > rootNode && array[k/2] < array[k] ) {
    // k 가 루트 노드가 아니고 부모 노드보다 값이 크다면, 부모 노드와 위치를 바꾼다.
    int temp = array[k];
    array[k] = array[k/2];
    array[k/2] = temp;

    k = k/2;
  }
}

/**
 * k 노드의 위치를 sink 방식으로 복구한다.
 *
 * @param k 정렬 상태를 위반하는 노드의 배열 인덱스
 */
private void sink(int k) {
  int N = array.length;
  while ( 2 * k <= N ) {
    // 최하단 노드까지 도달하지 않았다면
    int j = 2 * k;
    if (j < N && array[j] < array[j+1]) {
      // 두 자식 노드 중 더 큰 값을 가진 노드를 선택한다
      j++;
    }
    if (array[k] >= array[j]) {
      // 선택한 자식 노드가 sink 노드의 값보다 작으면 작업을 끝낸다
      break;
    }
    // 그렇지 않다면 선택한 자식 노드와 sink 노드의 위치를 바꾼다
    int temp = array[k];
    array[k] = array[j];
    array[j] = temp;

    k = j;
  }
}

/** 주어진 배열을 정렬한다. */
public static void sort(Comparable[] array) {
  final int n = array.length;

  for (int k = n / 2; k >= 1; k--) {
  // 힙을 구성한다(힙의 최하단 레벨은 sink 할 수 없으니 제외).
    sink(array, k, n);
  }

  int k = n;
  while (k > 1) {
  // 정렬 취합. 최하단부터 노드를 하나씩 root로 올려놓고 sink 시킨다.
    exchange(array, 1, k--);
    sink(array, 1, k);
  }
}

/**
 * k 인덱스 노드를 인덱스 n 지점까지 sink 시킨다.
 *
 * @param array 힙 노드가 보관되어 있는 배열
 * @param k     sink 대상 노드 인덱스
 * @param n     sink 대상이 되는 부분 힙의 경계 인덱스
 */
private static void sink(Comparable[] array, int k, int n) {
  while (2 * k <= n) {
    int j = 2 * k;
    if (j < n && less(array, j, j + 1)) {
      j++;
    }
    if (!less(array, k, j)) {
      break;
    }
    exchange(array, k, j);
    k = j;
  }
}

private static boolean less(Comparable[] array, int i, int j) {
  return array[i - 1].compareTo(array[j - 1]) < 0;
}

private static void exchange(Comparable[] array, int i, int j) {
  Comparable swap = array[i - 1];
  array[i - 1] = array[j - 1];
  array[j - 1] = swap;
}

/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
transient Object[] queue; // non-private to simplify nested class access

/**
 * An unbounded priority {@linkplain Queue queue} based on a priority heap.
 * The elements of the priority queue are ordered according to their
 * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
 * provided at queue construction time, depending on which constructor is
 * used.  A priority queue does not permit {@code null} elements.
 * A priority queue relying on natural ordering also does not permit
 * insertion of non-comparable objects (doing so may result in
 * {@code ClassCastException}).
 *
 * <p>The <em>head</em> of this queue is the <em>least</em> element
 * with respect to the specified ordering.  If multiple elements are
 * tied for least value, the head is one of those elements -- ties are
 * broken arbitrarily.  The queue retrieval operations {@code poll},
 * {@code remove}, {@code peek}, and {@code element} access the
 * element at the head of the queue.
 *
 * <p>A priority queue is unbounded, but has an internal
 * <i>capacity</i> governing the size of an array used to store the
 * elements on the queue.  It is always at least as large as the queue
 * size.  As elements are added to a priority queue, its capacity
 * grows automatically.  The details of the growth policy are not
 * specified.
 *
 * <p>This class and its iterator implement all of the
 * <em>optional</em> methods of the {@link Collection} and {@link
 * Iterator} interfaces.  The Iterator provided in method {@link
 * #iterator()} and the Spliterator provided in method {@link #spliterator()}
 * are <em>not</em> guaranteed to traverse the elements of
 * the priority queue in any particular order. If you need ordered
 * traversal, consider using {@code Arrays.sort(pq.toArray())}.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * Multiple threads should not access a {@code PriorityQueue}
 * instance concurrently if any of the threads modifies the queue.
 * Instead, use the thread-safe {@link
 * java.util.concurrent.PriorityBlockingQueue} class.
 *
 * <p>Implementation note: this implementation provides
 * O(log(n)) time for the enqueuing and dequeuing methods
 * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
 * linear time for the {@code remove(Object)} and {@code contains(Object)}
 * methods; and constant time for the retrieval methods
 * ({@code peek}, {@code element}, and {@code size}).
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
 * Java Collections Framework</a>.
 *
 * @since 1.5
 * @author Josh Bloch, Doug Lea
 * @param <E> the type of elements held in this queue
 */
@SuppressWarnings("unchecked")
public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

/**
 * Inserts the specified element into this priority queue.
 *
 * @return {@code true} (as specified by {@link Queue#offer})
 * @throws ClassCastException if the specified element cannot be
 *         compared with elements currently in this priority queue
 *         according to the priority queue's ordering
 * @throws NullPointerException if the specified element is null
 */
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length) {
        // 용량을 초과할 것 같으면 용량을 늘려준다
        grow(i + 1);
    }
    // 새로운 노드를 바닥에 추가하고, swim 시켜서 올려보낸다
    siftUp(i, e);

    // 사이즈를 갱신하고 끝낸다
    size = i + 1;
    return true;
}

/**
 * 생략: offer와 똑같다.
 */
public boolean add(E e) {
    return offer(e);
}

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x, queue, comparator);
    else
        siftUpComparable(k, x, queue);
}

private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    while (k > 0) {
        // 부모 노드
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        // 부모 노드보다 값이 크다면 swim을 멈춘다.
        if (key.compareTo((T) e) >= 0)
            break;
        // 그렇지 않다면 부모 노드와 자리를 바꾼다.
        es[k] = e;
        k = parent;
    }
    es[k] = key;
}

PriorityQueue<Comparable> queue = new PriorityQueue<>();
queue.addAll(List.of(5, 6, 12, 1, 95, 7, 53));

for (int i = 0; i < 7; i++) {
  System.out.print(queue.poll() + ", ");
}

public E poll() {
    final Object[] es;
    final E result;

    if ((result = (E) ((es = queue)[0])) != null) {
        modCount++;
        final int n;

        // 마지막 노드 x를 선택한다.
        final E x = (E) es[(n = --size)];
        // 마지막 노드가 있었던 곳에 null 을 입력한다.
        es[n] = null;
        if (n > 0) {
            // 노드 x 를 최상단부터 sink 시킨다
            final Comparator<? super E> cmp;
            if ((cmp = comparator) == null)
                siftDownComparable(0, x, es, n);
            else
                siftDownUsingComparator(0, x, es, n, cmp);
        }
    }
    return result;
}

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x, queue, size, comparator);
    else
        siftDownComparable(k, x, queue, size);
}

private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
    // assert n > 0;
    Comparable<? super T> key = (Comparable<? super T>)x;
    int half = n >>> 1;           // loop while a non-leaf
    while (k < half) {
        // 왼쪽과 오른쪽 두 자식 노드들 중 더 작은 노드를 선택한다.
        int child = (k << 1) + 1; // assume left child is least
        Object c = es[child];
        int right = child + 1;
        if (right < n &&
            ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
            c = es[child = right];
        // 자식 노드 선택이 끝났다면 자식과 값을 비교한다.
        // 자식 노드보다 값이 작다면 sink를 멈춘다.
        if (key.compareTo((T) c) <= 0)
            break;
        // 그렇지 않다면 자식 노드와 자리를 바꾼다.
        es[k] = c;
        k = child;
    }
    es[k] = key;
}