Binary Heap
Binary heap adalah pohon biner lengkap dengan satu aturan: tiap induk selalu lebih besar (atau lebih kecil) dari anak-anaknya, sehingga nilai ekstrem selalu berada di akar. Menyisip nilai baru berarti menaruhnya di ujung lalu menaikkannya (sift-up) menukar dengan induk selama lebih besar; mengambil nilai teratas berarti mengeluarkan akar, memindahkan node terakhir ke atas, lalu menurunkannya (sift-down). Inilah mesin di balik Antrian Prioritas. Visualisasi membangun heap lalu mengambil nilai maksimum.
Struktur yang membuat Antrian Prioritas cepat: triase IGD, penjadwal tugas sistem, dan algoritma Dijkstra semuanya memakai heap di dalamnya.
Pohon dengan aturan induk >= anak, jadi nilai maksimum selalu di akar; sisip = naik, ambil = turun, keduanya O(log n).
- ·Memahami sifat heap (induk >= anak)
- ·Menjelaskan sift-up saat menyisip dan sift-down saat mengambil
- ·Mengaitkan heap dengan Antrian Prioritas
- ·Simpan pohon biner lengkap sebagai array (anak indeks i = 2i+1 dan 2i+2).
- ·Sisip: taruh di ujung, tukar ke atas (sift-up) selama lebih besar dari induk.
- ·Ambil-max: keluarkan akar, node terakhir ke akar, turunkan (sift-down) tukar anak terbesar.
- ·Nilai maksimum selalu siap diambil di akar.
- ·Pohon biner
- ·Array sebagai representasi pohon
- ·Perbandingan nilai
- ·Mesin di dalam Antrian Prioritas (triase, penjadwalan).
- ·Dipakai algoritma Dijkstra dan A*.
- ·Heap Sort untuk mengurutkan data.
Kompleksitas O(log n) per sisip/ambil