PriorityQueue

Antrean di loket melayani orang yang datang lebih dulu, tetapi rumah sakit tidak: pasien paling gawat dilayani lebih dulu, berapa pun lama menunggunya. PriorityQueue membawa logika tersebut ke Collections Framework — elemen keluar bukan berdasarkan urutan masuk, melainkan berdasarkan prioritas yang ditentukan urutan alami (Comparable) atau Comparator pilihan kita. Struktur di baliknya adalah binary heap, penataan array cerdas yang hanya menjamin satu hal: elemen terkecil (menurut pembanding) selalu berada di depan. Pada Chapter penutup cabang antrean ini kita bedah heap tersebut, membuktikan bahwa iterasi PriorityQueue tidak terurut dan hanya poll yang terurut, lalu merakit studi kasus antrean tugas rumah tangga berbasis prioritas.

Binary Heap di Balik Layar #

PriorityQueue menyimpan elemennya dalam array biasa, tetapi membacanya sebagai pohon biner lengkap: elemen indeks 0 adalah akar, anak dari indeks i berada di 2i+1 dan 2i+2. Aturan tunggal yang dijaga adalah heap property — setiap parent bernilai ≤ anak-anaknya (untuk min-heap default). Susunan inilah mengapa array [1, 3, 2, 5, 9, 7] adalah heap yang sah sekaligus bukan array terurut:

Perhatikan diagram di atas: 1 sebagai akar lebih kecil dari 3 dan 2; 3 lebih kecil dari 5 dan 9; namun 3 dan 2 tidak diurutkan antar keduanya. Heap hanya menjanjikan “parent selalu lebih kecil dari anak”, bukan “keseluruhan terurut”. Dari janji minimalis itu lahir dua operasi murah: offer menempelkan elemen di ujung array lalu mengapungkannya (sift-up) dengan menukar posisi ke parent-nya selama lebih kecil — O(log n); poll mengambil akar, memindahkan elemen terakhir ke akar, lalu menenggelamkannya (sift-down) ke posisi yang sah — juga O(log n). peek yang hanya membaca akar berlangsung O(1).

Iterasi Tidak Terurut, poll Terurut #

Karena isi heap hanyalah array “setengah terurut”, iterasi dengan enhanced for-loop atau toString menjelajahi array dari indeks 0 sampai akhir — bukan dari yang terkecil sampai terbesar. Program berikut membuktikan perbedaan tersebut, sekaligus mencoba bentuk max-heap lewat Comparator.reverseOrder():

import java.util.*;

public class AntreanAngka {
    public static void main(String[] args) {
        // Urutan alami: angka terkecil keluar lebih dulu (min-heap).
        PriorityQueue<Integer> antrean = new PriorityQueue<>();
        antrean.addAll(List.of(5, 1, 7, 3, 9, 2));

        // Iterasi mengikuti susunan internal heap, BUKAN urutan terurut.
        System.out.println("Iterasi : " + antrean);

        StringBuilder keluar = new StringBuilder();
        while (!antrean.isEmpty()) {
            keluar.append(antrean.poll()).append(" ");
        }
        System.out.println("Poll    : " + keluar.toString().trim());

        // Comparator terbalik: angka terbesar keluar lebih dulu (max-heap).
        PriorityQueue<Integer> besarDulu = new PriorityQueue<>(Comparator.reverseOrder());
        besarDulu.addAll(List.of(5, 1, 7, 3, 9, 2));
        StringBuilder keluarBesar = new StringBuilder();
        while (!besarDulu.isEmpty()) {
            keluarBesar.append(besarDulu.poll()).append(" ");
        }
        System.out.println("Max-poll: " + keluarBesar.toString().trim());
    }
}

Output yang Dihasilkan:

Iterasi : [1, 3, 2, 5, 9, 7]
Poll    : 1 2 3 5 7 9
Max-poll: 9 7 5 3 2 1

Mari kita bedah baris-baris pentingnya:

1. Baris 9 (antrean.addAll(List.of(5, 1, 7, 3, 9, 2))): enam angka masuk tanpa urutan; tiap add di dalam addAll memicu sift-up sehingga setelah selesai, akar array adalah 1.
2. Baris 13 (Iterasi : [1, 3, 2, 5, 9, 7]): hasil iterasi berupa susunan heap mentah — sama dengan diagram pohon di atas. Bandingkan dengan Poll : 1 2 3 5 7 9 yang benar-benar terurut: hanya pengambilan berulang lewat poll yang menjanjikan urutan.
3. Baris 16-21 (loop poll): setiap poll mencabut akar lalu menenggelamkan penggantinya; setelah enam kali, angka keluar menurut urutan naik sempurna.
4. Baris 24 (new PriorityQueue<>(Comparator.reverseOrder())): satu Comparator mengubah heap menjadi max-heap — parent selalu ≥ anak — sehingga keluaran berubah menjadi 9 7 5 3 2 1.

Studi Kasus Antrean Tugas Berprioritas #

Kasus nyata prioritas jarang berupa angka telanjang — biasanya berupa objek dengan beberapa field. Program berikut mendefinisikan Tugas sebagai record (nama + angka prioritas), lalu menyusun antrean yang mendahulukan prioritas terkecil; tugas seprioritas dipecah berdasarkan nama agar hasilnya adil dan terprediksi:

import java.util.*;

public class AntreanTugas {
    record Tugas(String nama, int prioritas) { }

    public static void main(String[] args) {
        // Prioritas lebih kecil berarti lebih mendesak (1 paling depan).
        // Angka sama dipecah dengan urutan nama.
        Comparator<Tugas> urutan =
                Comparator.comparingInt(Tugas::prioritas)
                          .thenComparing(Tugas::nama);

        PriorityQueue<Tugas> antrean = new PriorityQueue<>(urutan);
        antrean.offer(new Tugas("Cuci piring", 3));
        antrean.offer(new Tugas("Bayar tagihan", 1));
        antrean.offer(new Tugas("Belanja", 2));
        antrean.offer(new Tugas("Kirim laporan", 1));

        System.out.println("Berikutnya (peek): " + antrean.peek());

        while (!antrean.isEmpty()) {
            Tugas tugas = antrean.poll();
            System.out.println("Mengerjakan: " + tugas);
        }
    }
}

Output yang Dihasilkan:

Berikutnya (peek): Tugas[nama=Bayar tagihan, prioritas=1]
Mengerjakan: Tugas[nama=Bayar tagihan, prioritas=1]
Mengerjakan: Tugas[nama=Kirim laporan, prioritas=1]
Mengerjakan: Tugas[nama=Belanja, prioritas=2]
Mengerjakan: Tugas[nama=Cuci piring, prioritas=3]

Poin bedahnya:

1. Baris 3 (record Tugas(...)): record otomatis menyediakan constructor, equals, hashCode, dan toString, sehingga definisi data tugas ringkas satu baris.
2. Baris 9-11 (Comparator.comparingInt(...).thenComparing(...)): perbandingan utama memakai field prioritas; bila angkanya sama, thenComparing(Tugas::nama) memutuskan lewat urutan alfabetis nama.
3. Baris 13 (new PriorityQueue<>(urutan)): comparator diteruskan ke konstruktor — tanpa argumen seperti ini, Tugas yang tidak Comparable akan melempar ClassCastException saat offer pertama.
4. Baris 19 (peek()): membaca kandidat berikutnya (prioritas 1, nama Bayar tagihan) tanpa mengganggu antrean.
5. Baris 21-24 (loop poll): urutan pengerjaan Bayar tagihan → Kirim laporan → Belanja → Cuci piring — dua tugas prioritas 1 keluar lebih dulu sesuai urutan nama, disusul prioritas 2 dan 3. Tugas yang masuk belakangan (Kirim laporan masuk setelah Belanja) melompat maju karena prioritasnya lebih tinggi.

Karakteristik yang Perlu Dicatat #

Dengan PriorityQueue, kita menuntaskan seluruh cabang antrean Collections Framework: FIFO murni lewat Queue, dua ujung lewat Deque, dan prioritas lewat heap. Masih tersisa satu keluarga besar yang sejak awal berdiri di luar hierarki Collection karena cara kerjanya berbeda — pemetaan kunci ke nilai pada Map dan keluarga implementasinya, yang menjadi fokus chapter-chapter berikutnya.

Referensi #

• Java API Specification: java.util.PriorityQueue
• Java API Specification: java.util.Queue
• Dev.java: The Java Collections Framework

import java.util.*;

public class AntreanAngka {
    public static void main(String[] args) {
        // Urutan alami: angka terkecil keluar lebih dulu (min-heap).
        PriorityQueue<Integer> antrean = new PriorityQueue<>();
        antrean.addAll(List.of(5, 1, 7, 3, 9, 2));

        // Iterasi mengikuti susunan internal heap, BUKAN urutan terurut.
        System.out.println("Iterasi : " + antrean);

        StringBuilder keluar = new StringBuilder();
        while (!antrean.isEmpty()) {
            keluar.append(antrean.poll()).append(" ");
        }
        System.out.println("Poll    : " + keluar.toString().trim());

        // Comparator terbalik: angka terbesar keluar lebih dulu (max-heap).
        PriorityQueue<Integer> besarDulu = new PriorityQueue<>(Comparator.reverseOrder());
        besarDulu.addAll(List.of(5, 1, 7, 3, 9, 2));
        StringBuilder keluarBesar = new StringBuilder();
        while (!besarDulu.isEmpty()) {
            keluarBesar.append(besarDulu.poll()).append(" ");
        }
        System.out.println("Max-poll: " + keluarBesar.toString().trim());
    }
}

import java.util.*;

public class AntreanTugas {
    record Tugas(String nama, int prioritas) { }

    public static void main(String[] args) {
        // Prioritas lebih kecil berarti lebih mendesak (1 paling depan).
        // Angka sama dipecah dengan urutan nama.
        Comparator<Tugas> urutan =
                Comparator.comparingInt(Tugas::prioritas)
                          .thenComparing(Tugas::nama);

        PriorityQueue<Tugas> antrean = new PriorityQueue<>(urutan);
        antrean.offer(new Tugas("Cuci piring", 3));
        antrean.offer(new Tugas("Bayar tagihan", 1));
        antrean.offer(new Tugas("Belanja", 2));
        antrean.offer(new Tugas("Kirim laporan", 1));

        System.out.println("Berikutnya (peek): " + antrean.peek());

        while (!antrean.isEmpty()) {
            Tugas tugas = antrean.poll();
            System.out.println("Mengerjakan: " + tugas);
        }
    }
}