Aplikasi antrian prioritas

Heap menjadi berguna ketika dipasangkan dengan kebutuhan yang paling sering muncul, yaitu memproses elemen berdasarkan prioritas, bukan berdasarkan urutan datang. Topik ini membungkus heap menjadi abstraksi antrian prioritas, lalu memakainya untuk tiga pola yang lazim pada soal maupun sistem nyata, yaitu seleksi top-k, penggabungan k list terurut, dan penjadwalan tugas. Semua demo ditulis dengan heapq pada Python dan PriorityQueue pada Java, lengkap dengan keluaran yang dijalankan sungguhan. Bagian akhir menyediakan daftar soal untuk dipraktikkan dari daftar latihan jalur ini.

Antrian prioritas sebagai ADT#

Antrian prioritas (priority queue) adalah tipe data abstrak (abstract data type, ADT), yaitu kontrak perilaku yang ditetapkan lebih dahulu sedangkan implementasinya boleh apa saja. Kontraknya terdiri atas dua operasi inti: masukkan satu elemen beserta urutannya, dan keluarkan elemen dengan prioritas tertinggi. Perbedaannya dengan antrian FIFO terletak pada aturan keluar, karena FIFO melayani yang datang lebih dulu, sedangkan antrian prioritas melayani yang paling penting. Layanan yang menangani kasus darurat lebih dahulu tanpa melihat urutan datang adalah contoh alaminya.

Heap adalah implementasi yang paling lazim karena kedua operasinya sama-sama $O(\log n)$. Alternatif lain menelan biaya lebih pada salah satu sisi: list terurut mengeluarkan ekstrem dalam $O(1)$ tetapi memasukkan dengan $O(n)$ karena pergeseran, sedangkan list tak terurut memasukkan dengan cepat tetapi mencari ekstrem dengan $O(n)$. Kombinasi dua operasi yang sama-sama murah itulah yang menjadikan heap tulang punggung antrian prioritas di hampir semua standard library.

Pemetaan konsepnya sederhana, yaitu prioritas disimpan sebagai bagian dari nilai, dan aturan min-heap atau max-heap menentukan yang mana keluar lebih dahulu. Bagian berikut memakai heapq sebagai wujud Pythonnya, lalu PriorityQueue sebagai wujud Javanya.

Mengenal heapq#

heapq adalah modul bawaan Python yang mengelola min-heap di atas list biasa. Fungsi utamanya meliputi heappush untuk menambah, heappop untuk mengeluarkan terkecil, heapify untuk mengubah list sembarang menjadi heap dalam $O(n)$, serta nlargest dan nsmallest untuk menjawab k ekstrem sekaligus. Demonstrasi berikut menambahkan tiga nilai lewat heappush, membaca isi internalnya, lalu mengosongkan heap dengan heappop berulang.

import heapq

heap = []
heapq.heappush(heap, 7)
heapq.heappush(heap, 2)
heapq.heappush(heap, 5)
print("isi internal heap :", heap)
print("heappop berulang  :", heapq.heappop(heap), heapq.heappop(heap), heapq.heappop(heap))

isi internal heap : [2, 7, 5]
heappop berulang  : 2 5 7

Baris pertama keluaran menegaskan sifat yang sudah dikenal, yaitu isi internal [2, 7, 5] bukan deretan terurut, melainkan array heap yang invariannya sah. Baris kedua memperlihatkan jaminan yang sesungguhnya penting, yaitu heappop selalu mengeluarkan 2, 5, lalu 7 tanpa peduli urutan pemasukannya. Nilai berada di list, sehingga seluruh operasi heapq bekerja pada array dengan rumus indeks yang sama seperti pada topik konsep heap. Di balik nlargest dan nsmallest, modul ini juga memakai heap ukuran kecil, sehingga keduanya lebih hemat daripada pengurutan penuh ketika k jauh lebih kecil daripada n.

Soal top-k dengan heap ukuran k#

Pertanyaan “cari k nilai terbesar dari n data” bisa dijawab dengan pengurutan penuh yang menelan $O(n \log n)$, padahal jawaban hanya membutuhkan k teratas. Heap ukuran k lebih hemat karena hanya menampung k kandidat terbaik sejauh ini. Alasan min-heap justru dipakai untuk mencari yang terbesar ada pada peran akarnya, yaitu menyimpan kandidat terlemah. Kandidat baru yang tidak lebih baik dari akar ditolak tanpa dipikirkan lagi, sedangkan kandidat yang lebih baik menggantikan akar tersebut. Ukuran heap tidak pernah melebihi k, sehingga setiap penggantian berbiaya $O(\log k)$ dan totalnya menjadi $O(n \log k)$.

Demo berikut mencari tiga nilai terbesar dari tujuh nilai tetap, lalu membandingkan hasilnya dengan heapq.nlargest sebagai pembanding mandiri.

"""Mencari tiga nilai terbesar dari data tetap dengan min-heap ukuran k."""
import heapq

nilai = [42, 17, 93, 8, 65, 29, 77]
k = 3

heap = []                        # min-heap berisi k kandidat terbaik sejauh ini
for x in nilai:
    if len(heap) < k:
        heapq.heappush(heap, x)
    elif x > heap[0]:
        heapq.heapreplace(heap, x)   # akar (kandidat terlemah) digantikan

print("heap akhir     :", heap)
print("tiga terbesar  :", sorted(heap, reverse=True))
print("heapq.nlargest :", heapq.nlargest(k, nilai))

heap akhir     : [65, 77, 93]
tiga terbesar  : [93, 77, 65]
heapq.nlargest : [93, 77, 65]

Penelusurannya terbaca dari data. Nilai 42, 17, dan 93 masuk sebagai tiga kandidat pertama, sedangkan 8 ditolak karena tidak lebih besar dari akar 17. Nilai 65 dan 77 masing-masing menggantikan kandidat terlemah saat itu, sehingga heap berakhir sebagai [65, 77, 93] dengan akar 65 sebagai kandidat terlemah yang tersisa. Hasil akhirnya sama dengan nlargest, hanya saja heap ukuran k tidak pernah menampung seluruh data sekaligus.

Penggabungan k list terurut#

Masalah kedua adalah menggabungkan k list yang masing-masing sudah terurut menjadi satu list terurut. Menjejalkan semuanya lalu mengurutkan menelan $O(N \log N)$ untuk $N$ elemen total, padahal setiap list sudah terurut dan informasi itu layak dipakai. Cara yang memanfaatkan informasi itu menaruh kepala setiap list ke dalam heap, mengeluarkan yang terkecil, lalu mendorong penggantinya dari list yang sama sampai semua habis. Isi heap tidak pernah lebih dari k elemen, sehingga biayanya $O(N \log k)$.

Satu detail penting menyangkut bentuk entri heap, yaitu tuple (nilai, nomor_list, indeks_elemen). Nilai menentukan urutan keluar, sedangkan nomor list memecah seri ketika dua list memuat nilai yang sama, sekaligus mencegah perbandingan berlanjut ke elemen yang tidak sebanding.

"""Menggabungkan tiga list terurut menjadi satu list terurut dengan heap."""
import heapq

list_terurut = [
    [1, 5, 9, 13],
    [2, 4, 9, 15],
    [3, 6, 8, 10],
]

# heap berisi kepala tiap list: (nilai, nomor list, indeks elemen)
heap = []
for nomor, lst in enumerate(list_terurut):
    heapq.heappush(heap, (lst[0], nomor, 0))

hasil = []
while heap:
    nilai, nomor, indeks = heapq.heappop(heap)
    hasil.append(nilai)
    if indeks + 1 < len(list_terurut[nomor]):
        berikutnya = list_terurut[nomor][indeks + 1]
        heapq.heappush(heap, (berikutnya, nomor, indeks + 1))

print("hasil gabungan :", hasil)

hasil gabungan : [1, 2, 3, 4, 5, 6, 8, 9, 9, 10, 13, 15]

Keluaran memuat dua nilai 9 karena dua list sumber memang sama-sama menampungnya, dan keduanya keluar rapi tanpa error perbandingan berkat pemecah seri pada tuple. Pola heap berisi kepala list ini tidak terbatas pada angka, karena elemennya boleh berupa objek apa pun yang punya kunci urutan, misalnya gabungan beberapa berkas log yang masing-masing sudah terurut menurut waktu.

Penjadwalan tugas#

Pola ketiga menangani tugas yang datang sewaktu-waktu, dengan aturan prioritas tertinggi dikerjakan lebih dahulu. Heap menyimpan pasangan prioritas dan nama tugas, lalu setiap langkah penjadwalan cukup memanggil heappop untuk mengambil tugas berikutnya. Karena heapq adalah min-heap, prioritas dinegasikan agar tugas bernilai besar keluar lebih dahulu, sesuai catatan pada bagian heapq. Pendekatan ini juga cocok untuk tugas yang jumlahnya bertambah sepanjang hari, karena heap tidak pernah menuntut seluruh datanya sejak awal.

"""Menjadwalkan tugas menurut prioritas dengan heapq."""
import heapq

tugas = [
    (3, "cadangkan berkas"),
    (9, "perbaiki error"),
    (1, "perbarui dokumentasi"),
    (7, "tulis laporan"),
]

# heapq hanya min-heap: prioritas dinegasikan agar nilai besar keluar lebih dulu
heap = [(-prioritas, nama) for prioritas, nama in tugas]
heapq.heapify(heap)

print("urutan pengerjaan:")
while heap:
    prioritas_neg, nama = heapq.heappop(heap)
    print(f"  prioritas {-prioritas_neg} : {nama}")

urutan pengerjaan:
  prioritas 9 : perbaiki error
  prioritas 7 : tulis laporan
  prioritas 3 : cadangkan berkas
  prioritas 1 : perbarui dokumentasi

Tugas dengan prioritas 9 keluar pertama meskipun pemasukannya urutan kedua, sedangkan prioritas 1 menunggu sampai terakhir. Bila tugas baru datang di tengah eksekusi, satu heappush sudah cukup untuk memasukkannya ke dalam persaingan, dan biaya tiap langkah tetap $O(\log n)$ terhadap jumlah tugas yang menunggu. Pola ini sederhana namun mencakup banyak kasus, misalnya antrean pekerjaan cadangan yang memproses berkas terbesar lebih dahulu, atau penentuan giliran piket menurut tingkat urgensinya. Untuk aturan tambahan seperti “prioritas sama, yang datang lebih dulu dilayani lebih dulu”, kunci heap cukup diperluas menjadi tuple (prioritas, waktu_datang) sehingga urutannya tetap tunggal.

PriorityQueue pada Java#

Kelas java.util.PriorityQueue adalah wujud antrian prioritas pada Java, berbasis binary heap dengan perilaku min-heap secara default. Urutannya dapat diatur penuh lewat Comparator, yaitu objek yang membandingkan dua elemen, mulai dari urutan alami sampai urutan berdasarkan atribut tertentu. Program berikut mengulang soal top-k dengan min-heap ukuran k yang diberi Comparator.naturalOrder() secara eksplisit.

import java.util.PriorityQueue;
import java.util.Comparator;

public class TopTiga {
    public static void main(String[] args) {
        int[] nilai = {42, 17, 93, 8, 65, 29, 77};
        int k = 3;

        // min-heap ukuran k: naturalOrder() menempatkan kandidat terlemah di akar
        Comparator<Integer> urutanNaik = Comparator.naturalOrder();
        PriorityQueue<Integer> heap = new PriorityQueue<>(urutanNaik);

        for (int x : nilai) {
            if (heap.size() < k) {
                heap.add(x);
            } else if (urutanNaik.compare(x, heap.peek()) > 0) {
                heap.poll();   // kandidat terlemah digantikan oleh yang baru
                heap.add(x);
            }
        }

        // keluarkan isi heap, lalu sajikan menurun sebagai peringkat
        int[] hasil = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            hasil[i] = heap.poll();
        }
        for (int i = 0; i < k; i++) {
            System.out.println("peringkat " + (i + 1) + " : " + hasil[i]);
        }
    }
}

peringkat 1 : 93
peringkat 2 : 77
peringkat 3 : 65

Keluaran menampilkan 93, 77, lalu 65 sebagai tiga nilai terbesar, sama persis dengan hasil heapq pada Python untuk data yang sama. Metode dasarnya mengikuti pola yang sudah dikenal, yaitu add atau offer untuk memasukkan, peek untuk membaca akar tanpa mengeluarkannya, dan poll untuk mengeluarkan akarnya, semuanya dengan biaya $O(\log n)$. Antrian ini tidak menerima null, karena nilai kosong tidak dapat dibandingkan dengan pembanding mana pun. Pembanding yang sama mudah dibalik: Comparator.reverseOrder() mengubah heap menjadi max-heap, sedangkan Comparator.comparingInt(Tugas::prioritas).reversed() mengurutkan objek tugas menurut atribut prioritasnya untuk penjadwalan. Satu catatan perilaku yang sering mengejutkan, yaitu iterasi langsung atas PriorityQueue tidak menghasilkan urutan terurut, karena hanya poll() yang menjamin elemen terkecil keluar lebih dahulu.

Soal untuk dipraktikkan#

Soal-soal berikut dipilih dari daftar latihan jalur ini karena paling tepat dijawab dengan heap atau antrian prioritas. Kerjakan berurutan karena tingkatnya menanjak.

1. Last Stone Weight : pemanasan pop dua terbesar berulang kali, pola max-heap yang paling polos.
2. Kth Largest Element in a Stream : penerapan langsung min-heap ukuran k yang dipertahankan seiring data mengalir.
3. Kth Largest Element in an Array : seleksi k terbesar tanpa pengurutan penuh, dengan peluang membandingkan pendekatan heap dan quickselect.
4. Top K Frequent Elements : frekuensi dihitung terlebih dahulu, lalu heap mengurutkan berdasarkan frekuensi, bukan nilai mentah.
5. K Closest Points to Origin : kunci prioritas berupa jarak kuadrat, melatih pemilihan kunci pada heap ukuran k.
6. Merge k Sorted Lists : versi klasik pola penggabungan k list dengan heap berisi kepala tiap list.
7. Task Scheduler : penjadwalan dengan penghitungan tugas dan aturan jeda, menguji pengelolaan isi heap yang terus berubah.

Ringkasan#

• Antrian prioritas adalah ADT dengan dua operasi inti, dan heap mengimplementasikan keduanya dalam $O(\log n)$.
• heapq menyediakan heappush, heappop, heapify, serta nlargest dan nsmallest, sedangkan negasi prioritas mengakali sifat min-heapnya.
• Min-heap ukuran k menjawab top-k dalam $O(n \log k)$ karena akarnya selalu kandidat terlemah yang siap digantikan.
• Penggabungan k list terurut dan penjadwalan tugas memakai heap yang isinya tetap kecil, dan PriorityQueue pada Java mengatur urutan lewat Comparator.

Referensi#

• heapq — Heap queue algorithm — Python Software Foundation — dokumentasi heappush, heappop, heapify, nlargest, dan nsmallest yang dipakai pada seluruh demo Python.
• Priority queue — Wikipedia — definisi ADT antrian prioritas dan perbandingan implementasinya.