Heap dan Priority Queue

BST menjanjikan akses ke nilai mana pun dalam O(log n), tetapi banyak aplikasi hanya bertanya satu hal: “mana yang paling kecil (atau paling besar)?” Server antrian tugas ingin pekerjaan paling prioritas, algoritma pathfinding ingin jarak terpendek berikutnya, dan heap sort ingin elemen terkecil berulang kali. Untuk pertanyaan seperti itu, heap menawarkan perjanjian yang lebih longgar daripada BST: ia tidak menjaga urutan penuh, hanya menjamin elemen ekstrem selalu berada di puncak — dan itu cukup untuk bekerja dalam O(log n). Chapter ini membangun min-heap manual di atas array, lalu membandingkannya dengan std::priority_queue.

Properti Heap dan Representasi Array #

Min-heap adalah binary tree dengan dua syarat. Pertama, heap property: nilai setiap node tidak lebih besar dari nilai anak-anaknya, sehingga node terkecil selalu berada di root. Kedua, bentuk tree (shape property): terisi penuh level demi level dari kiri ke kanan, tanpa lubang. Syarat kedua terdengar kaku, tetapi justru di sanalah kecualiannya — tree dengan bentuk seperti itu bisa disimpan rapi di array tanpa pointer sama sekali:

Karena level terisi urut, anak-anak node i selalu berada di 2*i+1 dan 2*i+2. Max-heap adalah kebalikannya: setiap node tidak lebih kecil dari anak-anaknya, sehingga nilai terbesar di puncak. Perhatikan bahwa heap bukan struktur terurut: dua subtree mana pun bisa saling tukar tanpa melanggar aturan, dan itulah sumber efisiensinya — urutan parsial lebih murah dijaga daripada urutan penuh BST.

Implementasi Min-heap Manual #

Semua pekerjaan heap ada di dua prosedur: siftUp mengangkat elemen yang terlalu kecil menuju puncak, dan siftDown menurunkan elemen yang terlalu besar menuju daun. Program berikut membangun min-heap dari data {5, 3, 8, 1, 9}, menampilkan array internalnya, lalu mengosongkannya dengan pop berulang:

// Min-heap manual di atas vector, lalu perbandingan dengan std::priority_queue.
#include <functional>
#include <iostream>
#include <queue>
#include <vector>

class MinHeap {
public:
    void push(int nilai) {
        data_.push_back(nilai);
        siftUp(static_cast<int>(data_.size()) - 1);
    }

    int top() const { return data_[0]; }  // elemen terkecil; wajib tak kosong

    void pop() {
        data_[0] = data_.back();   // elemen terakhir naik ke puncak
        data_.pop_back();
        siftDown(0);
    }

    bool kosong() const { return data_.empty(); }

    void tampilkanArray() const {
        for (std::size_t i = 0; i < data_.size(); ++i) {
            if (i > 0) std::cout << ' ';
            std::cout << data_[i];
        }
        std::cout << '\n';
    }

private:
    std::vector<int> data_;

    static int induk(int i) { return (i - 1) / 2; }
    static int anakKiri(int i) { return 2 * i + 1; }
    static int anakKanan(int i) { return 2 * i + 2; }

    void siftUp(int i) {  // angkat elemen kecil menuju puncak
        while (i > 0 && data_[i] < data_[induk(i)]) {
            std::swap(data_[i], data_[induk(i)]);
            i = induk(i);
        }
    }

    void siftDown(int i) {  // turunkan elemen besar menuju daun
        int n = static_cast<int>(data_.size());
        while (true) {
            int terkecil = i;
            int kiri = anakKiri(i);
            int kanan = anakKanan(i);
            if (kiri < n && data_[kiri] < data_[terkecil]) terkecil = kiri;
            if (kanan < n && data_[kanan] < data_[terkecil]) terkecil = kanan;
            if (terkecil == i) break;
            std::swap(data_[i], data_[terkecil]);
            i = terkecil;
        }
    }
};

int main() {
    MinHeap heap;
    for (int nilai : {5, 3, 8, 1, 9}) {
        heap.push(nilai);
    }
    std::cout << "Representasi array min-heap: ";
    heap.tampilkanArray();
    std::cout << "top(): " << heap.top() << '\n';

    std::cout << "Pop berulang (heap sort mini): ";
    bool pertama = true;
    while (!heap.kosong()) {
        if (!pertama) std::cout << ' ';
        std::cout << heap.top();
        pertama = false;
        heap.pop();
    }
    std::cout << '\n';

    // std::priority_queue: max-heap secara default
    std::priority_queue<int> maks;
    for (int nilai : {5, 3, 8, 1, 9}) {
        maks.push(nilai);
    }
    std::cout << "priority_queue default (maks): ";
    pertama = true;
    while (!maks.empty()) {
        if (!pertama) std::cout << ' ';
        std::cout << maks.top();
        pertama = false;
        maks.pop();
    }
    std::cout << '\n';

    // Min-heap lewat comparator std::greater<int>
    std::priority_queue<int, std::vector<int>, std::greater<int>> minimum;
    for (int nilai : {5, 3, 8, 1, 9}) {
        minimum.push(nilai);
    }
    std::cout << "priority_queue greater (min) : ";
    pertama = true;
    while (!minimum.empty()) {
        if (!pertama) std::cout << ' ';
        std::cout << minimum.top();
        pertama = false;
        minimum.pop();
    }
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

Representasi array min-heap: 1 3 8 5 9
top(): 1
Pop berulang (heap sort mini): 1 3 5 8 9
priority_queue default (maks): 9 8 5 3 1
priority_queue greater (min) : 1 3 5 8 9

Bedah baris penting:

1. Baris 9-12 (push): elemen baru ditambahkan di ujung array — satu-satunya posisi yang menjaga shape property — lalu siftUp memperbaiki heap property.
2. Baris 39-44 (siftUp): selama elemen lebih kecil dari induknya, keduanya ditukar dan posisi naik ke induk(i). Paling buruk O(log n) karena tinggi tree.
3. Baris 16-21 (pop): mengambil puncak berarti mengosongkan root; elemen terakhir array dinaikkan mengisi posisi itu, lalu siftDown menurunkannya ke tempat yang pantas.
4. Baris 46-59 (siftDown): setiap langkah memilih di antara node, anak kiri, dan anak kanan yang terkecil (baris 49-53), menukarnya, lalu lanjut ke bawah.
5. Baris 35-37: tiga formula indeks — seluruh relasi induk-anak dihitung aritmetika, tanpa pointer.
6. Baris 63-68: hasil push {5, 3, 8, 1, 9} tersimpan sebagai array 1 3 8 5 9; root bernilai 1 memenuhi min-heap property, dan top() langsung membacanya.
7. Baris 70-78: pop berulang selalu mengeluarkan nilai terkecil yang tersisa: 1 3 5 8 9 — mengosongkan heap dengan pop berarti menghasilkan urutan menaik.

Perhatikan array 1 3 8 5 9: urutannya memang belum terurut penuh (8 sebelum 5), dan itu sah untuk heap. Yang dijamin hanyalah induk tidak lebih besar dari anak-anaknya.

std::priority_queue #

std::priority_queue adalah container adapter yang menyembunyikan heap di balik antarmuka push, top, dan pop. Secara default ia memakai max-heap — kebalikan dari implementasi manual kita di atas — karena kasus “ambil yang terpenting” lebih umum daripada “ambil yang terkecil”. Output program menunjukkan keduanya: tanpa argumen tambahan, angka keluar terbesar lebih dulu; dengan comparator std::greater<int>, perilakunya berubah menjadi min-heap dan angka keluar terkecil lebih dulu.

Pemilihan comparator mengikuti pola yang sama seperti std::sort yang sudah kita pakai di section STL: default berbasis operator<, dan greater<T> untuk membalik urutan. Untuk tipe buatan sendiri, kita cukup menyediakan operator< atau comparator eksplisit tanpa menyentuh algoritma heap-nya.

Heap Sort: Pratinjau #

Pop berulang pada min-heap menghasilkan data menaik — itulah inti heap sort: bangun heap dari seluruh data (O(n)), lalu pop sebanyak n kali (O(log n) per pop) untuk mendapatkan urutan lengkap dalam O(n log n) total. Versi maksimalnya bekerja in-place di satu array dan akan kita kaitkan kembali pada chapter Sorting Algorithms. Untuk kebutuhan praktis harian, std::sort hampir selalu cukup; heap unggul saat data terus berubah dan kita butuh “ekstrem terkini” berulang kali, bukan satu kali sortir di akhir.

Heap memberi kita akses instan ke satu elemen ekstrem. Ketika hubungan yang penting bukan urutan melainkan keterhubungan — jaringan, peta jalan, relasi pertemanan — kita butuh struktur yang lebih bebas lagi: graph, topik chapter berikutnya.

Rujukan resmi: std::priority_queue dan std::make_heap .