public class HeapManual {

    // Min-heap berbasis array: anak kiri = 2i+1, anak kanan = 2i+2, induk = (i-1)/2.
    private final int[] isi = new int[64];
    private int ukuran;

    // Penghitung tukar posisi (swap) saat sift-up dan sift-down.
    static long tukar;

    public static void main(String[] args) {
        HeapManual heap = new HeapManual();
        System.out.println("=== Sisip satu per satu: 50, 30, 70, 20, 40 ===");
        for (int nilai : new int[] {50, 30, 70, 20, 40}) {
            tukar = 0;
            heap.sisip(nilai);
            System.out.printf("sisip(%d) -> tukar posisi: %d%n", nilai, tukar);
        }

        System.out.println();
        System.out.println("Isi array (level-order): " + heap.bacaArray());
        System.out.println("Struktur pohon:");
        heap.cetakLevel();

        System.out.println();
        System.out.println("=== poll() berulang: elemen keluar terurut naik ===");
        while (heap.ukuran > 0) {
            tukar = 0;
            int terkecil = heap.poll();
            System.out.printf("poll() = %2d, tukar posisi: %d%n", terkecil, tukar);
        }
    }

    void sisip(int nilai) {
        isi[ukuran] = nilai;
        int i = ukuran;
        ukuran++;
        // sift-up: angkat nilai baru selama lebih kecil dari induknya.
        while (i > 0) {
            int induk = (i - 1) / 2;
            if (isi[i] < isi[induk]) {
                tukarPosisi(i, induk);
                i = induk;
            } else {
                break;
            }
        }
    }

    int poll() {
        int terkecil = isi[0];
        isi[0] = isi[ukuran - 1];   // elemen terakhir naik ke akar
        ukuran--;
        // sift-down: turunkan akar baru sampai lebih kecil dari kedua anaknya.
        int i = 0;
        while (true) {
            int kiri = 2 * i + 1;
            int kanan = 2 * i + 2;
            int terkecilIdx = i;
            if (kiri < ukuran && isi[kiri] < isi[terkecilIdx]) {
                terkecilIdx = kiri;
            }
            if (kanan < ukuran && isi[kanan] < isi[terkecilIdx]) {
                terkecilIdx = kanan;
            }
            if (terkecilIdx == i) {
                break;
            }
            tukarPosisi(i, terkecilIdx);
            i = terkecilIdx;
        }
        return terkecil;
    }

    void tukarPosisi(int a, int b) {
        tukar++;
        int sementara = isi[a];
        isi[a] = isi[b];
        isi[b] = sementara;
    }

    String bacaArray() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < ukuran; i++) {
            if (i > 0) {
                sb.append(", ");
            }
            sb.append(isi[i]);
        }
        return sb.append(']').toString();
    }

    void cetakLevel() {
        int level = 0;
        int awal = 0;
        while (awal < ukuran) {
            int akhir = Math.min(awal + (1 << level), ukuran);
            StringBuilder sb = new StringBuilder("  Level " + level + ":");
            for (int i = awal; i < akhir; i++) {
                sb.append(' ').append(isi[i]);
            }
            System.out.println(sb);
            awal = akhir;
            level++;
        }
    }
}