std::priority_queue

std::priority_queue adalah container adapter STL yang membungkus heap berbasis array menjadi antarmuka yang ringkas untuk priority queue. Secara default container ini berperilaku sebagai max-heap, namun cukup mengganti satu parameter template untuk mendapatkan min-heap atau comparator custom untuk tipe data buatan sendiri. Pada Chapter ini kita akan membedah tiga parameter template std::priority_queue, mendemonstrasikan tiga konfigurasi umum (max-heap, min-heap, custom struct), dan menjelaskan batasan-batasan API yang membuat container ini kurang fleksibel dibanding implementasi heap manual — khususnya ketiadaan iterasi, operasi decrease-key, dan akses elemen acak. Pada akhir chapter kita akan paham kapan memilih std::priority_queue dan kapan menulis class heap sendiri.

Apa Itu `std::priority_queue` #

std::priority_queue<T, Container, Compare> adalah container adapter yang menyajikan struktur priority queue berbasis heap. Tiga parameter template:

Parameter	Default	Fungsi
`T`	(wajib)	Tipe elemen
`Container`	`std::vector<T>`	Container underlying (harus random-access)
`Compare`	`std::less<T>`	Functor comparator — `true` bila a harus di bawah b

Compare = std::less<T> menghasilkan max-heap (elemen terbesar di top). Mengganti ke std::greater<T> menghasilkan min-heap.

Aturan Default: Max-Heap #

Deklarasi tanpa parameter template tambahan menghasilkan max-heap:

cpp
std::priority_queue<int> pq;  // sama dengan std::priority_queue<int, std::vector<int>, std::less<int>>

Operasi yang tersedia:

Operasi	Kompleksitas	Keterangan
`push(v)`	`O(log n)`	Tambah elemen
`pop()`	`O(log n)`	Hapus elemen prioritas tertinggi (top)
`top()`	`O(1)`	Akses elemen prioritas tertinggi (read-only)
`empty()`, `size()`	`O(1)`	Status
`swap(other)`	`O(1)`	Tukar isi dengan priority queue lain

Min-Heap: `std::greater<T>` #

Untuk membuat min-heap, gunakan tiga parameter template secara eksplisit:

cpp
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

Kunci perubahan: Compare = std::greater<int>, sehingga cmp(a, b) = (a > b) true bila a harus berada di bawah b — artinya elemen kecil naik ke top.

Kode: Tiga Konfigurasi `std::priority_queue` #

cpp
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <string>

struct Task {
    int priority;
    std::string name;
};

// Comparator untuk min-heap berdasarkan priority
struct TaskCmp {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority > b.priority;  // lower priority value = higher priority
    }
};

int main() {
    // === 1. Default: max-heap of int ===
    std::priority_queue<int> maxpq;
    for (int x : {4, 10, 3, 5, 1}) maxpq.push(x);
    std::cout << "max-heap (default):\n  ";
    while (!maxpq.empty()) { std::cout << maxpq.top() << ' '; maxpq.pop(); }
    std::cout << '\n';

    // === 2. Min-heap: std::greater<int> ===
    std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;
    for (int x : {4, 10, 3, 5, 1}) minpq.push(x);
    std::cout << "min-heap (greater<int>):\n  ";
    while (!minpq.empty()) { std::cout << minpq.top() << ' '; minpq.pop(); }
    std::cout << '\n';

    // === 3. Custom comparator untuk struct ===
    std::priority_queue<Task, std::vector<Task>, TaskCmp> tasks;
    tasks.push({5, "deploy"});
    tasks.push({1, "fix-bug-kritis"});
    tasks.push({3, "code-review"});
    tasks.push({2, "patch-keamanan"});
    std::cout << "priority queue custom (priority rendah = didahulukan):\n";
    while (!tasks.empty()) {
        const auto& t = tasks.top();
        std::cout << "  [P" << t.priority << "] " << t.name << '\n';
        tasks.pop();
    }

    return 0;
}

Output yang Dihasilkan:

text
max-heap (default):
  10 5 4 3 1 
min-heap (greater<int>):
  1 3 4 5 10 
priority queue custom (priority rendah = didahulukan):
  [P1] fix-bug-kritis
  [P2] patch-keamanan
  [P3] code-review
  [P5] deploy

Bedah Kode Baris-per-Baris #

struct Task { int priority; std::string name; };: struct sederhana yang akan disimpan di priority queue. Karena struct, kita tidak bisa memakai std::less<Task> langsung (operator < tidak terdefinisi untuk struct), sehingga wajib menyediakan comparator custom.
struct TaskCmp { bool operator()(const Task& a, const Task& b) const { return a.priority > b.priority; } };: functor comparator. Mengembalikan true bila a harus berada di bawah b. Untuk min-heap (priority rendah = di top), kembalikan a.priority > b.priority.
std::priority_queue<int> maxpq;: deklarasi default — semua parameter template pakai default, menghasilkan max-heap int.
std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;: min-heap dengan eksplisit tiga parameter. Wajib menulis std::vector<int> di tengah karena parameter Container harus dispesifikasi sebelum Compare (C++ tidak mendukung argumen template default di tengah tanpa argumen sebelumnya).
std::priority_queue<Task, std::vector<Task>, TaskCmp> tasks;: priority queue custom — elemen Task, container std::vector<Task>, comparator TaskCmp. Pola yang sama berlaku untuk struct apa pun.
maxpq.top(): akses elemen prioritas tertinggi (max). Mengembalikan const int& — read-only.
maxpq.pop(): hapus elemen top. Tidak mengembalikan nilai — bila ingin menggunakannya, simpan dulu lewat top() sebelum pop().
Output max-heap: 10 5 4 3 1 — urutan descending.
Output min-heap: 1 3 4 5 10 — urutan ascending.
Output custom: task dengan priority terkecil (1, 2, 3, 5) keluar lebih dulu — sesuai semantik comparator a.priority > b.priority.

Pola Comparator Custom untuk Struct #

Comparator custom dapat ditulis dalam beberapa bentuk:

Bentuk 1: Functor (struct dengan `operator()`) #

cpp
struct TaskCmp {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority > b.priority;
    }
};
std::priority_queue<Task, std::vector<Task>, TaskCmp> pq;

Bentuk 2: Lambda (C++20+ dengan `decltype`) #

cpp
auto cmp = [](const Task& a, const Task& b) { return a.priority > b.priority; };
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> pq(cmp);

Bentuk 3: Fungsi Bebas dengan `std::function` #

cpp
bool task_cmp(const Task& a, const Task& b) { return a.priority > b.priority; }
std::priority_queue<Task, std::vector<Task>,
                    bool(*)(const Task&, const Task&)> pq(task_cmp);

Batasan API `std::priority_queue` #

Container adapter ini sengaja menyembunyikan container underlying untuk menjaga invariant heap. Konsekuensinya, beberapa operasi tidak tersedia:

Tidak Ada Iterasi #

cpp
std::priority_queue<int> pq;
// for (int x : pq) { ... }   // ERROR: tidak ada begin()/end()
// pq[0]                        // ERROR: tidak ada operator[]

Container underlying std::vector disembunyikan sepenuhnya. Untuk iterasi elemen (misalnya debugging), gunakan container terpisah atau implementasi heap manual.

Tidak Ada Decrease-Key #

Operasi decrease-key (menurunkan prioritas elemen tertentu) tidak tersedia. Padahal operasi ini penting untuk algoritma Dijkstra versi optimal O(E + V log V). Karena std::priority_queue tidak mengizinkan akses elemen acak, kita harus workaround:

Push ulang elemen dengan priority baru, biarkan versi lama tetap di queue (lazy deletion).
Saat pop, lewati elemen yang sudah kedaluwarsa (gunakan timestamp atau visited flag).

Tidak Bisa Merge #

Tidak ada operasi merge(other) seperti pada std::set. Bila ingin menggabungkan dua priority queue, pop satu per satu dan push ke yang lain — O(n log n).

Hanya Bisa Akses Top #

Hanya top() yang bisa diakses. Tidak ada cara untuk melihat atau memodifikasi elemen lain tanpa pop() berulang.

Workaround Lazy Deletion untuk Dijkstra #

Pola lazy deletion untuk Dijkstra dengan std::priority_queue:

cpp
#include <iostream>
#include <queue>
#include <vector>
#include <utility>

// Mengembalikan jarak terpendek dari src ke semua node pada graph adjacency list
std::vector<long long> dijkstra_lazy(const std::vector<std::vector<std::pair<int, int>>>& adj,
                                     int src) {
    int n = static_cast<int>(adj.size());
    const long long INF = 1e18;
    std::vector<long long> dist(n, INF);
    // Min-heap: pair<distance, node>
    std::priority_queue<std::pair<long long, int>,
                        std::vector<std::pair<long long, int>>,
                        std::greater<std::pair<long long, int>>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        // Lazy deletion: bila distance sudah lebih baik, skip
        if (d > dist[u]) continue;

        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    // Graph: 4 node, edges berbobot
    std::vector<std::vector<std::pair<int, int>>> adj(4);
    adj[0] = {{1, 1}, {4, 2}};
    adj[1] = {{1, 2}, {2, 3}};
    adj[2] = {{5, 3}};
    adj[3] = {};

    auto dist = dijkstra_lazy(adj, 0);
    std::cout << "Jarak dari node 0:\n";
    for (int i = 0; i < 4; ++i) {
        std::cout << "  ke node " << i << " = " << dist[i] << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
Jarak dari node 0:
  ke node 0 = 0
  ke node 1 = 1
  ke node 2 = 2
  ke node 3 = 3

Bedah Kode Baris-per-Baris #

std::priority_queue<std::pair<long long, int>, ..., std::greater<...>> pq;: min-heap berisi pair (distance, node). std::greater<pair> membandingkan pair lexicographically — pertama distance, lalu node. Hasilnya: pair dengan distance terkecil keluar lebih dulu.
dist[src] = 0; pq.push({0, src});: inisialisasi sumber dengan jarak 0.
auto [d, u] = pq.top(); pq.pop();: ambil elemen dengan distance terkecil. Structured binding (C++17) mengurai pair menjadi dua variabel.
if (d > dist[u]) continue;: lazy deletion. Bila d (distance pada saat push) lebih besar dari dist[u] (distance terkini), elemen ini sudah kedaluwarsa — skip. Inilah cara menghindari decrease-key yang tidak didukung STL.
for (auto [w, v] : adj[u]): iterasi tetangga. w = bobot edge, v = node tujuan.
if (dist[u] + w < dist[v]): cek relaksasi. Bila jarak baru lebih kecil, perbarui dan push ke queue. Versi lama dist[v] masih ada di queue — akan di-skip oleh lazy deletion di atas.
Output: jarak terpendek dari node 0 ke setiap node lain. Node 3 dicapai melalui 0 → 1 → 3 dengan total bobot 1 + 2 = 3.

Kapan Menggunakan `std::priority_queue` vs Heap Manual #

Kriteria	`std::priority_queue`	Heap Manual
Kode butuh cepat ditulis	✅ Cocok	❌ Terlalu verbose
Butuh decrease-key	❌ Tidak didukung	✅ Bisa custom
Butuh iterasi elemen	❌ Tidak ada `begin/end`	✅ Array bisa diakses
Butuh akses elemen acak	❌ Hanya `top()`	✅ Bisa custom
Performa ekstrem (mis. CP)	✅ STL dioptimasi	Tergantung implementasi
Hanya butuh `push`/`pop`/`top`	✅ Pilihan default	Overkill

Mengakses Container Underlying (Untuk Debug) #

Secara standar tidak ada cara publik untuk mengakses Container underlying. Trik yang umum dipakai untuk debugging:

cpp
// Hanya untuk debugging — bukan pola produksi
template <typename PQ>
void debug_print(const PQ& pq) {
    PQ copy = pq;             // copy, lalu pop satu per satu
    while (!copy.empty()) {
        std::cout << copy.top() << ' ';
        copy.pop();
    }
    std::cout << '\n';
}

Trik ini meng-copy seluruh priority queue (mahal!) lalu pop satu per satu. Untuk produksi, simpan container terpisah.

Ringkasan #

std::priority_queue<T, Container, Compare> adalah adapter untuk priority queue berbasis heap.
Default = max-heap. Min-heap: ganti Compare menjadi std::greater<T>.
Comparator custom untuk struct: gunakan functor (struct Cmp { bool operator()(...); };).
API minimal: push, pop, top, empty, size, swap.
Tidak mendukung iterasi, akses elemen acak, atau decrease-key.
Lazy deletion: solusi untuk Dijkstra — push ulang elemen, skip yang kedaluwarsa saat pop.
Untuk skenario yang butuh operasi lanjutan (decrease-key, indexed), tulis heap manual atau gunakan std::set<pair>.

Pada Chapter berikutnya kita akan mengaplikasikan priority queue untuk masalah konkret pertama: mencari k elemen terbesar dan terkecil dari sebuah koleksi data dengan kompleksitas O(n log k).

Apa Itu std::priority_queue #

Aturan Default: Max-Heap #

Min-Heap: std::greater<T> #

Kode: Tiga Konfigurasi std::priority_queue #

Bedah Kode Baris-per-Baris #

Pola Comparator Custom untuk Struct #

Bentuk 1: Functor (struct dengan operator()) #

Bentuk 2: Lambda (C++20+ dengan decltype) #

Bentuk 3: Fungsi Bebas dengan std::function #

Batasan API std::priority_queue #

Tidak Ada Iterasi #

Tidak Ada Decrease-Key #

Tidak Bisa Merge #

Hanya Bisa Akses Top #

Workaround Lazy Deletion untuk Dijkstra #

Bedah Kode Baris-per-Baris #

Kapan Menggunakan std::priority_queue vs Heap Manual #

Mengakses Container Underlying (Untuk Debug) #

Ringkasan #

Apa Itu `std::priority_queue` #

Min-Heap: `std::greater<T>` #

Kode: Tiga Konfigurasi `std::priority_queue` #

Bentuk 1: Functor (struct dengan `operator()`) #

Bentuk 2: Lambda (C++20+ dengan `decltype`) #

Bentuk 3: Fungsi Bebas dengan `std::function` #

Batasan API `std::priority_queue` #

Kapan Menggunakan `std::priority_queue` vs Heap Manual #