public class HeapifyManual {

    // Penghitung tukar posisi (swap) selama penyetaraan heap.
    static long tukar;

    public static void main(String[] args) {
        // Data terurut turun: kasus paling berat bagi sisip satu per satu.
        int[] data = {7, 6, 5, 4, 3, 2, 1};

        System.out.println("Data awal                  : " + baca(data));
        heapify(data);
        System.out.println("Setelah heapify            : " + baca(data));
        System.out.println("Tukar posisi saat heapify  : " + tukar);
        System.out.println("Hasil valid sebagai min-heap: " + validMinHeap(data));

        System.out.println();
        tukar = 0;
        int[] hasilSisip = sisipBerurutan(new int[] {7, 6, 5, 4, 3, 2, 1});
        System.out.println("Setelah sisip satu per satu: " + baca(hasilSisip));
        System.out.println("Tukar posisi saat sisip    : " + tukar);
        System.out.println("Hasil valid sebagai min-heap: " + validMinHeap(hasilSisip));
    }

    // Heapify: sift-down dari node terakhir yang punya anak, naik ke akar.
    static void heapify(int[] a) {
        for (int i = a.length / 2 - 1; i >= 0; i--) {
            siftDown(a, i, a.length);
        }
    }

    static int[] sisipBerurutan(int[] data) {
        int[] heap = new int[data.length];
        int ukuran = 0;
        for (int nilai : data) {
            heap[ukuran] = nilai;
            int i = ukuran;
            ukuran++;
            while (i > 0) {                     // sift-up
                int induk = (i - 1) / 2;
                if (heap[i] < heap[induk]) {
                    tukar++;
                    int sementara = heap[i];
                    heap[i] = heap[induk];
                    heap[induk] = sementara;
                    i = induk;
                } else {
                    break;
                }
            }
        }
        return heap;
    }

    static void siftDown(int[] a, int i, int ukuran) {
        while (true) {
            int kiri = 2 * i + 1;
            int kanan = 2 * i + 2;
            int terkecil = i;
            if (kiri < ukuran && a[kiri] < a[terkecil]) {
                terkecil = kiri;
            }
            if (kanan < ukuran && a[kanan] < a[terkecil]) {
                terkecil = kanan;
            }
            if (terkecil == i) {
                break;
            }
            tukar++;
            int sementara = a[i];
            a[i] = a[terkecil];
            a[terkecil] = sementara;
            i = terkecil;
        }
    }

    static boolean validMinHeap(int[] a) {
        for (int i = 1; i < a.length; i++) {
            if (a[i] < a[(i - 1) / 2]) {
                return false;   // anak lebih kecil dari induk: melanggar aturan
            }
        }
        return true;
    }

    static String baca(int[] a) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < a.length; i++) {
            if (i > 0) {
                sb.append(", ");
            }
            sb.append(a[i]);
        }
        return sb.append(']').toString();
    }
}