// 第 15 周 – 堆排序：O(n log n)，原地，不稳定
// 运行：java HeapSort.java
import java.util.Arrays;

public class HeapSort {

    // 这里下标从 0 开始：i 的孩子是 2i+1 和 2i+2
    static void siftDown(int[] a, int i, int n) {
        while (2 * i + 1 < n) {
            int c = 2 * i + 1;
            if (c + 1 < n && a[c + 1] > a[c]) c++;
            if (a[i] >= a[c]) return;
            int t = a[i]; a[i] = a[c]; a[c] = t;
            i = c;
        }
    }

    static void heapSort(int[] a, boolean trace) {
        int n = a.length;
        // 1. 自底向上建堆 – O(n)
        for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
        if (trace) System.out.println("  heap:      " + Arrays.toString(a));
        // 2. 把最大值（根）交换到数组末尾，把堆看作少了一个元素 – n · O(log n)
        for (int end = n - 1; end > 0; end--) {
            int t = a[0]; a[0] = a[end]; a[end] = t;
            siftDown(a, 0, end);
        }
    }

    public static void main(String[] args) {
        int[] a = { 40, 70, 20, 90, 50, 80, 60, 10 };
        System.out.println("  start:     " + Arrays.toString(a));
        heapSort(a, true);
        System.out.println("  sorted:    " + Arrays.toString(a));

        int[] big = new java.util.Random(1).ints(1_000_000).toArray();
        long t0 = System.nanoTime();
        heapSort(big.clone(), false);
        System.out.printf("heapsort of 1 000 000 elements: %.1f ms%n", (System.nanoTime() - t0) / 1e6);
    }
}