Penerapan Heap

Heap bukan sekadar struktur data teoritis — ia adalah tulang punggung banyak algoritma penting: Dijkstra, Prim, Huffman coding, median-of-stream, scheduling berprioritas, dan top-k frequent. Pola umum di balik semua penerapan tersebut adalah “perlu akses cepat ke elemen prioritas tertinggi (maksimum/minimum) berulang kali”. Pada Chapter ini kita akan membedah lima penerapan heap yang paling sering muncul, mengimplementasikan tiga di antaranya secara konkret dalam C++, dan melihat bagaimana pilihan varian heap (max/min) ditentukan oleh kebutuhan algoritma. Pada akhir chapter kita akan paham bahwa hampir semua algoritma yang berinteraksi dengan “antrian berprioritas” dapat diimplementasikan dengan heap sebagai fondasi.

Pola Umum: “Repeated Extract-Min/Max” #

Hampir semua penerapan heap mengikuti pola berikut:

1. Inisialisasi: masukkan elemen-elemen awal ke heap.
2. Loop utama: extract-min/max → proses → push elemen baru (bila perlu) — berulang hingga heap kosong atau kondisi terpenuhi.

Pola ini menjaga invariant bahwa elemen prioritas tertinggi selalu tersedia di top() dengan biaya O(1), dan operasi pop/push hanya O(log n). Total kompleksitas biasanya O((n + m) log n) di mana n adalah ukuran heap dan m adalah jumlah operasi.

Penerapan 1: Dijkstra (Single-Source Shortest Path) #

Algoritma Dijkstra mencari jarak terpendek dari satu node sumber ke semua node lain pada graph berbobot non-negatif. Heap digunakan untuk mengambil node dengan jarak terkecil yang belum diproses — extract-min pada min-heap berisi (distance, node).

Aturan #

• Inisialisasi: dist[src] = 0, push (0, src) ke min-heap.
• Loop: extract-min (d, u). Bila d > dist[u] (lazy deletion), skip. Bila tidak, relaksasi setiap edge (u, v, w) — bila dist[u] + w < dist[v], perbarui dist[v] dan push (dist[v], v).

Kompleksitas #

O((V + E) log V) dengan lazy deletion. Implementasi dengan decrease-key khusus (Fibonacci heap) dapat mencapai O(E + V log V), namun std::priority_queue tidak mendukung decrease-key secara langsung.

Penerapan 2: Prim (Minimum Spanning Tree) #

Algoritma Prim membangun Minimum Spanning Tree (MST) dengan strategi greedy: mulai dari node acak, perluas tree dengan menambahkan edge berbobot minimum yang menghubungkan node-tree ke node non-tree. Heap menyimpan kandidat edge.

Aturan #

• Inisialisasi: push (0, src) ke min-heap. Tandai src sebagai “dalam tree” saat di-extract.
• Loop: extract-min (weight, node). Bila node sudah dalam tree, skip. Bila tidak, tambahkan ke tree, lalu untuk setiap edge (node, neighbor, w) ke neighbor yang belum dalam tree, push (w, neighbor) ke heap.

Kompleksitas #

O(E log V) dengan lazy deletion. Sama dengan Dijkstra — keduanya essentially algoritma yang sama dengan sedikit perbedaan interpretasi.

Penerapan 3: Median of Stream #

Diberikan stream angka yang datang satu per satu, hitung median dari semua angka yang sudah dilihat. Pendekatan sort-ulang setiap kali berbiaya O(n² log n) — terlalu mahal. Dengan dua heap, kita dapat O(log n) per insert dan O(1) per query.

Aturan #

• Max-heap lo menyimpan setengah elemen terkecil (root = elemen terbesar di setengah bawah).
• Min-heap hi menyimpan setengah elemen terbesar (root = elemen terkecil di setengah atas).
• Invariant ukuran: |lo| == |hi| atau |lo| == |hi| + 1.
• Median: bila ukuran ganjil, root lo. Bila genap, rata-rata kedua root.

Mekanisme Insert #

Tambah elemen baru x:

1. Push x ke lo, lalu pindahkan root lo ke hi (rebalance awal — pastikan semua elemen lo ≤ semua elemen hi).
2. Bila |lo| < |hi|, pindahkan root hi ke lo (jaga invariant ukuran).

Setelah rebalance, root lo adalah elemen tengah (median untuk ukuran ganjil), atau rata-rata kedua root adalah median (ukuran genap).

Kode: Tiga Penerapan Konkret #

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

// === 1. Median of stream: dua heap ===
class MedianFinder {
    std::priority_queue<int> lo;  // max-heap (setengah bawah)
    std::priority_queue<int, std::vector<int>, std::greater<int>> hi;  // min-heap (setengah atas)

public:
    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top());
        lo.pop();
        // Jaga size: lo boleh 1 lebih besar dari hi
        if (lo.size() < hi.size()) {
            lo.push(hi.top());
            hi.pop();
        }
    }

    double findMedian() const {
        if (lo.size() > hi.size()) return lo.top();
        return (lo.top() + hi.top()) / 2.0;
    }
};

// === 2. Scheduling: prioritaskan deadline terdekat ===
struct Job {
    int deadline;
    int profit;
    std::string name;
};

struct JobCmp {
    // min-heap by deadline: deadline terdekat di top
    bool operator()(const Job& a, const Job& b) const {
        return a.deadline > b.deadline;
    }
};

// === 3. Top-k frequent (versi ringkas) ===
std::vector<std::pair<std::string, int>>
top_k_frequent(const std::vector<std::string>& words, int k) {
    std::unordered_map<std::string, int> freq;
    for (const auto& w : words) freq[w]++;

    using P = std::pair<int, std::string>;
    auto cmp = [](const P& a, const P& b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    };
    std::priority_queue<P, std::vector<P>, decltype(cmp)> pq(cmp);
    for (const auto& [w, f] : freq) {
        pq.push({f, w});
        if (static_cast<int>(pq.size()) > k) pq.pop();
    }
    std::vector<std::pair<std::string, int>> res;
    while (!pq.empty()) {
        res.emplace_back(pq.top().second, pq.top().first);
        pq.pop();
    }
    return res;
}

int main() {
    // === Demo Median of Stream ===
    std::cout << "=== Median of Stream ===\n";
    MedianFinder mf;
    for (int x : {5, 15, 1, 3, 8, 7, 9, 2}) {
        mf.addNum(x);
        std::cout << "add " << x << " -> median = " << mf.findMedian() << '\n';
    }

    // === Demo Scheduling ===
    std::cout << "\n=== Job Scheduling (deadline terdekat diutamakan) ===\n";
    std::vector<Job> jobs = {
        {2, 100, "A"}, {1, 50, "B"}, {2, 80, "C"}, {3, 20, "D"}, {1, 30, "E"}
    };
    std::priority_queue<Job, std::vector<Job>, JobCmp> pq;
    for (const auto& j : jobs) pq.push(j);
    while (!pq.empty()) {
        const auto& j = pq.top();
        std::cout << "  deadline=" << j.deadline << " profit=" << j.profit
                  << " (" << j.name << ")\n";
        pq.pop();
    }

    // === Demo Top-k Frequent ===
    std::cout << "\n=== Top-2 Frequent Words ===\n";
    std::vector<std::string> words = {"apple", "banana", "apple", "cherry",
                                       "banana", "apple", "cherry", "cherry"};
    auto top = top_k_frequent(words, 2);
    for (const auto& [w, f] : top) {
        std::cout << "  " << w << " (" << f << "x)\n";
    }
    return 0;
}

Output yang Dihasilkan:

=== Median of Stream ===
add 5 -> median = 5
add 15 -> median = 10
add 1 -> median = 5
add 3 -> median = 4
add 8 -> median = 5
add 7 -> median = 6
add 9 -> median = 7
add 2 -> median = 6

=== Job Scheduling (deadline terdekat diutamakan) ===
  deadline=1 profit=50 (B)
  deadline=1 profit=30 (E)
  deadline=2 profit=80 (C)
  deadline=2 profit=100 (A)
  deadline=3 profit=20 (D)

=== Top-2 Frequent Words ===
  cherry (3x)
  apple (3x)

Bedah Kode Baris-per-Baris #

1. std::priority_queue<int> lo;: max-heap (default) menyimpan setengah elemen terkecil. Root = elemen terbesar di setengah bawah = elemen tengah untuk ukuran ganjil.
2. std::priority_queue<int, std::vector<int>, std::greater<int>> hi;: min-heap menyimpan setengah elemen terbesar. Root = elemen terkecil di setengah atas.
3. lo.push(num); hi.push(lo.top()); lo.pop();: strategi rebalance — push ke lo, lalu pindahkan root lo (elemen terbesar di setengah bawah) ke hi. Operasi ini memastikan semua elemen lo ≤ semua elemen hi.
4. if (lo.size() < hi.size()) { lo.push(hi.top()); hi.pop(); }: jaga invariant ukuran |lo| ≥ |hi|. Bila hi lebih besar, pindahkan root hi ke lo.
5. double findMedian() const: bila |lo| > |hi| (ukuran total ganjil), median = root lo. Bila |lo| == |hi| (genap), median = rata-rata kedua root.
6. struct JobCmp { bool operator()(...) const { return a.deadline > b.deadline; } };: comparator untuk min-heap berdasarkan deadline. Job dengan deadline terdekat = root.
7. std::priority_queue<Job, std::vector<Job>, JobCmp> pq;: priority queue custom untuk Job. Deadline terdekat di-extract pertama.
8. Output scheduling: deadline 1 (B, E) keluar pertama, lalu deadline 2 (C, A), terakhir deadline 3 (D). Urutan dalam deadline sama bergantung urutan insert — heap tidak stabil.
9. std::unordered_map<std::string, int> freq;: hitung frekuensi O(n) rata-rata.
10. if (static_cast<int>(pq.size()) > k) pq.pop();: pertahankan ukuran heap ≤ k. Root = elemen dengan frekuensi terkecil di k teratas — akan di-pop bila elemen baru lebih besar.
11. Output top-k frequent: cherry dan apple sama-sama muncul 3 kali — keduanya masuk top-2. Tiebreak lexicographic: apple < cherry, namun karena min-heap di-pop dari root, hasil akhir diurutkan ulang dengan sort.

Penerapan 4: Huffman Coding #

Huffman coding membangun prefix code optimal untuk kompresi data. Strategi: setiap iterasi, gabungkan dua node dengan frekuensi terkecil menjadi satu node internal. Heap menyimpan kandidat node berdasarkan frekuensi.

Aturan #

1. Hitung frekuensi setiap simbol.
2. Push setiap simbol sebagai node daun ke min-heap berdasarkan frekuensi.
3. Selama heap berisi lebih dari 1 node: extract dua node terkecil, gabungkan menjadi node baru dengan frekuensi = jumlah keduanya, push ke heap.
4. Node terakhir yang tersisa adalah root Huffman tree.

Kompleksitas #

O(n log n) untuk n simbol — n kali extract-min + n-1 kali push.

Penerapan 5: A* Search #

A* adalah algoritma pencarian jalur yang menggabungkan greedy best-first dan Dijkstra. Heap menyimpan kandidat node dengan skor f(n) = g(n) + h(n) (jarak tempuh + heuristik).

Aturan #

• Inisialisasi: push (h(src), src) ke min-heap.
• Loop: extract-min (f, u). Bila u adalah goal, selesai. Bila sudah diproses, skip. Bila tidak, untuk setiap tetangga v, hitung g(v) = g(u) + w(u, v), push (g(v) + h(v), v) bila g(v) lebih kecil dari sebelumnya.

Kompleksitas #

O((V + E) log V) dengan lazy deletion. Efisiensi sangat tergantung kualitas heuristik h — heuristik admissible (tidak overestimate) menjamin optimality.

Tabel Ringkas Penerapan Heap #

Memilih Varian Heap Berdasarkan Skenario #

• Butuh elemen minimum (Dijkstra, Prim, Huffman): min-heap.
• Butuh elemen maksimum (scheduling profit tertinggi, heap sort): max-heap.
• Butuh keduanya sekaligus (median of stream): dua heap berlawanan arah.
• Ukuran heap tetap k (top-k, merge k arrays): heap berukuran k dengan lazy pop.

Penerapan di Sistem Nyata #

• Operasi system scheduler: kernel Linux menggunakan red-black tree untuk fair scheduling (CFS), namun konsepnya serupa — priority queue dengan operasi extract-min O(log n).
• Event-driven simulation: discrete event simulation menggunakan priority queue untuk menentukan event berikutnya yang akan diproses berdasarkan timestamp.
• Network router QoS: antrian paket berprioritas menggunakan heap untuk menentukan paket mana yang dikirim lebih dulu.
• Load balancer: distribusi request ke server dengan beban tersedikit menggunakan min-heap berisi (load, server).

Komparasi Heap vs Alternatif #

std::priority_queue adalah pilihan default — sederhana, cepat, dan memori efisien. Bila butuh decrease-key atau iterasi, beralih ke std::set<std::pair<priority, value>> atau implementasi heap manual.

Ringkasan #

• Heap adalah tulang punggung algoritma yang berulang mengambil elemen prioritas tertinggi: Dijkstra, Prim, Huffman, A*.
• Median of stream: dua heap berlawanan arah (max + min), O(log n) per insert, O(1) per query.
• Scheduling: priority queue custom dengan comparator berdasarkan deadline/prioritas.
• Top-k frequent: kombinasi hash map + heap berukuran k.
• Pilihan varian heap ditentukan oleh operasi utama yang dibutuhkan: min, max, atau keduanya.
• std::priority_queue adalah pilihan default; beralih ke std::set atau heap manual bila butuh operasi lanjutan.

Pada Section berikutnya kita akan beralih ke struktur data linier terkait — graph — dan melihat bagaimana algoritma-algoritma graph memanfaatkan struktur yang sudah kita pelajari di Section ini.