// 15. hét – Kupacrendezés: O(n log n), helyben, nem stabil
// Futtatás: java HeapSort.java
import java.util.Arrays;

public class HeapSort {

    // Itt 0-tól indexelünk: i gyerekei 2i+1 és 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. Kupacépítés alulról felfelé – O(n)
        for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
        if (trace) System.out.println("  kupac:     " + Arrays.toString(a));
        // 2. A maximumot (gyökér) a tömb végére cseréljük, a kupacot eggyel kisebbnek tekintjük – 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("  kezdet:    " + Arrays.toString(a));
        heapSort(a, true);
        System.out.println("  rendezett: " + 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("1 000 000 elem kupacrendezése: %.1f ms%n", (System.nanoTime() - t0) / 1e6);
    }
}