Queue pada Chapter sebelumnya melayani siapa pun yang datang lebih dulu. Banyak sistem nyata tidak semodem itu: unit gawat darurat melayani pasien paling kritis walau datang paling akhir; penjadwal tugas memilih proses dengan prioritas tertinggi. Struktur untuk kebutuhan tersebut adalah priority queue: elemen keluar bukan berdasarkan urutan kedatangan, melainkan berdasarkan prioritas. Implementasi terbaiknya adalah binary heap — pohon lengkap yang hidup rapi di dalam sebuah array tanpa satu pun pointer. Bab ini membangun heap secara manual lengkap dengan penghitung tukar posisi, membuktikan bahwa poll berbiaya O(log n), lalu menunjukkan cara cepat membangun heap dari data acak lewat heapify.
Heap sebagai Pohon yang Tinggal di Array #
Binary heap adalah pohon biner lengkap (complete binary tree) — semua level terisi penuh kecuali level terakhir yang terisi dari kiri. Kelengkapan inilah yang memungkinkan trik penyimpanan: node diletakkan di array sesuai urutan level, sehingga posisi anak dan induk bisa dihitung dengan aritmetika. Anak kiri node ke-i berada di indeks 2i + 1, anak kanan di 2i + 2, dan induk di (i - 1) / 2. Tidak ada field next, tidak ada object Node — hanya satu array dan tiga rumus. Heap menjaga satu invariant: setiap induk tidak lebih besar (min-heap) atau tidak lebih kecil (max-heap) daripada anak-anaknya. Akibatnya elemen terkecil selalu duduk di indeks 0, siap diambil dalam satu langkah.
Sisip dengan Sift-Up dan Poll dengan Sift-Down #
Dua operasi inti menjaga invariant dengan cara berlawanan. Sisip menaruh nilai baru di slot kosong paling akhir lalu sift-up: nilai naik bertukar posisi dengan induknya selama nilainya lebih kecil. Poll mengambil akar, memindahkan elemen terakhir ke akar, lalu sift-down: nilai turun bertukar posisi dengan anak terkecilnya sampai berhenti:
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++;
}
}
}Output yang Dihasilkan:
=== Sisip satu per satu: 50, 30, 70, 20, 40 ===
sisip(50) -> tukar posisi: 0
sisip(30) -> tukar posisi: 1
sisip(70) -> tukar posisi: 0
sisip(20) -> tukar posisi: 2
sisip(40) -> tukar posisi: 0
Isi array (level-order): [20, 30, 70, 50, 40]
Struktur pohon:
Level 0: 20
Level 1: 30 70
Level 2: 50 40
=== poll() berulang: elemen keluar terurut naik ===
poll() = 20, tukar posisi: 1
poll() = 30, tukar posisi: 1
poll() = 40, tukar posisi: 1
poll() = 50, tukar posisi: 0
poll() = 70, tukar posisi: 0Output membuktikan dua sifat penting heap. Pertama, cetak level memperlihatkan struktur pohonnya: akar 20 di Level 0, anak-anaknya 30 dan 70 di Level 1, lalu 50 dan 40 di Level 2 — setiap induk memang lebih kecil dari anaknya. Kedua, lima poll() mengembalikan 20, 30, 40, 50, 70 — terurut naik sempurna. Mari kita bedah mekanismenya:
- Baris 37-50 (
sisip): nilai baru menempati indeksukuran(slot paling kanan level terakhir), lalu loop membandingkannya dengan induk di(i-1)/2. Sisip nilai 20 memicu 2 tukar posisi karena 20 harus naik dua level melewati 50 lalu 30. - Baris 52-74 (
poll): akar disimpan lebih dulu untuk dikembalikan, elemen terakhir dipindahkan ke akar, lalu loop memilih anak terkecil dan bertukar dengannya. Setiap tukar memindahkan nilai tepat satu level ke bawah, jadi jumlah tukar tidak pernah melampaui tinggi pohon. - Baris 76-82 (
tukarPosisi): penghitungtukardinaikkan di satu tempat saja — semua laporan kompleksitas pada program ini berangkat dari angka di method ini.
Inilah jawaban mengapa poll adalah O(log n): pohon lengkap dengan n node punya tinggi ⌊log₂ n⌋, dan sift-down menuruni paling banyak satu tukar per level. Pada output di atas, heap berisi 5 elemen (tinggi 2) dan tidak ada poll yang melebihi 1 tukar; heap sejuta elemen pun maksimal butuh 20 tukar. Bandingkan dengan array terurut yang harus menggeser rata-rata n/2 elemen per sisip, atau BST degenerate yang bisa memburuk jadi O(n).
Heapify Membangun Heap Sekali Jalan #
Kalau seluruh data sudah tersedia, menyisipkan satu per satu bukanlah cara tercepat. Heapify bekerja dari bawah ke atas: mulai dari node terakhir yang masih punya anak (indeks n/2 - 1) hingga akar, setiap node di-sift-down sekali. Program berikut membandingkan dua jalur pada data terurut turun — kasus terberat bagi sisip berurutan:
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();
}
}Output yang Dihasilkan:
Data awal : [7, 6, 5, 4, 3, 2, 1]
Setelah heapify : [1, 3, 2, 4, 6, 7, 5]
Tukar posisi saat heapify : 4
Hasil valid sebagai min-heap: true
Setelah sisip satu per satu: [1, 4, 2, 7, 5, 6, 3]
Tukar posisi saat sisip : 10
Hasil valid sebagai min-heap: trueKedua jalur menghasilkan min-heap yang sah — method validMinHeap memeriksa invariant anak-tidak-lebih-kecil-dari-induk untuk keduanya — tetapi biayanya berbeda: heapify hanya 4 tukar posisi, sisip berurutan 10. Alasannya struktural: sift-up pada sisip berurutan dilakukan dari level paling bawah yang penuh node (mayoritas node berada di sana), sementara heapify memproses node bawah dengan sift-down paling pendek dan hanya sedikit node di dekat akar yang menurun jauh. Penjumlahan matematisnya memberi heapify total kerja O(n), dibanding O(n log n) pada kasus terburuk sisip berurutan. Inilah dasar dari heap sort yang efisien dan dari Collections.sort versi lama.
PriorityQueue di Pustaka Java #
Kelas java.util.PriorityQueue adalah min-heap siap pakai dengan API queue: offer(x) menyisip dalam O(log n), poll() mengambil dan menghapus elemen terkecil dalam O(log n), peek() membaca elemen terkecil dalam O(1) tanpa menghapus. Urutan “terkecil” ditentukan natural ordering elemen, atau Comparator yang dilewatkan ke konstruktor — comparator terbalik langsung mengubahnya menjadi max-heap. Satu syarat penting: elemen tidak boleh diubah setelah dimasukkan, karena perubahan field yang dipakai comparator membuat posisi elemen di heap tidak lagi sah.
Heap memproses satu prioritas tertinggi dalam sekali poll. Relasi antar data di dunia nyata sering berbentuk jaringan yang lebih kaya dari hierarki — kota terhubung ke banyak kota lain. Struktur berikutnya, graph, bersama algoritma penelusurannya menjadi bahasa untuk jaringan semacam itu.
Referensi #
- Oracle: java.util PriorityQueue
- Oracle: java.util Comparator
- VisuAlgo — Binary Heap
- Cormen dkk., Introduction to Algorithms (CLRS), Bab 6
Berkas Sumber
Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.
HeapifyManual.java
Unduh berkaspublic 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();
}
}
HeapManual.java
Unduh berkaspublic 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++;
}
}
}