18.2.堆排序

\(18.2\)Heap Sort

1.The step of Heap Sorting

  The simplest method to implement sorting via heap is to put the whole array into a heap, and pick out top of the heap one by one.

  However, this method will lead to unnecessarily memory waste, for we can do heap sorting in place without creating a new heap.

2.Step impletation

  \(a.\)Basic Heap operation

private static void sink(Comparable[] pq, int k, int n) {
    while (2 * k <= n) {
        int j = 2 * k;//left child
        if (j < n && less(pq, j, j + 1)) j += 1;
        if (!less(pq, k, j)) break;
        swap(pq, k, j);
        k = j;
    }
}

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

private static void swap(Object[] pq, int i, int j) {
    Object o = pq[i - 1];
    pq[i - 1] = pq[j - 1];
    pq[j - 1] = o;
}

  \(b.\)Heap Sorting

  The in place heap sorting use the following step: 1. Sink the element in the array one by one, so that the array forms a heap.

2. Pop the front element one by one, and move the popped element to the back of the array.

public static void sort(Comparable[] pq) {
    int n = pq.length;
    //heapify
    for (int k = n / 2; k >= 1; k --) sink(pq, k, n);

    //sort and swap
    int k = n;
    while (k > 1) {
        //pop the heaptop
        swap(pq, 1, k--);
        //why k--?Because the kth element is sorted, so we only need to care about the k-1 th
        //maintain the heap property
        sink(pq, 1, k);
    }

}