Min-Heap dan Max-Heap

Heap memiliki dua varian utama yang dibedakan oleh arah relasi parent-anak: max-heap (parent selalu lebih besar atau sama dengan anak-anaknya) dan min-heap (parent selalu lebih kecil atau sama dengan anak-anaknya). Kedua varian tersebut memiliki struktur pohon yang identik — perbedaannya hanyalah pada operator perbandingan yang digunakan saat menjaga heap-order. Pada Chapter ini kita akan membedah kedua varian, memetakan penggunaan khas untuk masing-masing, dan mengimplementasikan satu class heap generik berbasis template C++ yang dapat berperilaku sebagai max-heap atau min-heap hanya dengan mengganti comparator. Pada akhir chapter kita akan paham bahwa max-heap dan min-heap adalah dua instance dari struktur yang sama, dan switch antar keduanya tidak memerlukan perubahan logika inti.

Definisi Max-Heap dan Min-Heap #

Max-Heap #

Max-heap adalah heap dengan sifat: untuk setiap node i (kecuali root), v[parent(i)] ≥ v[i]. Akibatnya, elemen maksimum selalu berada di root (indeks 0 array). Max-heap cocok untuk skenario yang memerlukan akses cepat ke elemen terbesar: scheduling berbasis prioritas tertinggi, heap sort (extract max berulang), atau algoritma Prim (extract max weight edge — bila dianalogikan).

Min-Heap #

Min-heap adalah heap dengan sifat: untuk setiap node i (kecuali root), v[parent(i)] ≤ v[i]. Akibatnya, elemen minimum selalu berada di root. Min-heap cocok untuk skenario yang memerlukan akses cepat ke elemen terkecil: algoritma Dijkstra (extract node dengan jarak minimum), Huffman coding (extract dua node dengan frekuensi terkecil), atau merge k sorted arrays (extract elemen terkecil berikutnya).

Perbandingan Singkat #

Kode: Heap Generik dengan Comparator #

Inti dari kedua varian heap sama: sift up membandingkan node dengan parent, lalu menukar bila perlu. Satu-satunya perbedaan adalah arah perbandingan. Daripada menulis dua class, kita gunakan template C++ dengan comparator — sama seperti cara STL std::priority_queue bekerja.

#include <iostream>
#include <vector>
#include <functional>

// Heap generik dengan comparator. less = max-heap, greater = min-heap.
template <typename T, typename Compare>
class Heap {
    std::vector<T> data;
    Compare cmp;   // cmp(a, b) true bila a harus berada di bawah b

    int parent(int i) const { return (i - 1) / 2; }

    void sift_up(int i) {
        while (i > 0 && cmp(data[parent(i)], data[i])) {
            std::swap(data[parent(i)], data[i]);
            i = parent(i);
        }
    }

public:
    bool empty() const { return data.empty(); }
    std::size_t size() const { return data.size(); }
    const T& top() const { return data.front(); }

    void push(const T& v) {
        data.push_back(v);
        sift_up(static_cast<int>(data.size()) - 1);
    }
};

int main() {
    std::vector<int> nums = {4, 10, 3, 5, 1, 8, 2, 7, 6, 9};

    Heap<int, std::less<int>> maxH;     // max-heap
    Heap<int, std::greater<int>> minH;  // min-heap
    for (int x : nums) { maxH.push(x); minH.push(x); }

    std::cout << "Root max-heap : " << maxH.top() << '\n';
    std::cout << "Root min-heap : " << minH.top() << '\n';
    return 0;
}

Output yang Dihasilkan:

Root max-heap : 10
Root min-heap : 1

Bedah Kode Baris-per-Baris #

1. template <typename T, typename Compare>: parameter template pertama adalah tipe elemen (T), parameter kedua adalah functor comparator. Kita menggunakan type erasure lewat template — compiler menghasilkan kode khusus untuk setiap pasangan (T, Compare).
2. Compare cmp;: instance comparator. std::less<int> adalah struct dengan operator()(a, b) yang mengembalikan a < b. std::greater<int> mengembalikan a > b.
3. while (i > 0 && cmp(data[parent(i)], data[i])): kondisi loop adalah “parent harus ditukar dengan anak”. Untuk max-heap (std::less), cmp(parent, child) adalah parent < child — true bila parent lebih kecil, sehingga swap terjadi dan elemen besar naik. Untuk min-heap (std::greater), cmp(parent, child) adalah parent > child — true bila parent lebih besar, sehingga swap dan elemen kecil naik.
4. std::swap(data[parent(i)], data[i]);: tukar parent dengan anak, lalu pindahkan indeks i ke posisi parent untuk iterasi berikutnya.
5. Heap<int, std::less<int>> maxH;: instantiate max-heap untuk int.
6. Heap<int, std::greater<int>> minH;: instantiate min-heap untuk int. Kode class Heap sama persis — hanya comparator yang berbeda.
7. Output: max-heap root 10 (maksimum), min-heap root 1 (minimum). Kedua heap dibangun dari array yang sama [4, 10, 3, 5, 1, 8, 2, 7, 6, 9] tetapi menghasilkan root berbeda karena arah perbandingan berbeda.

Cara Mengubah Max-Heap menjadi Min-Heap #

Konversi max-heap menjadi min-heap tidak mengubah algoritma — hanya membalikkan operator perbandingan. Berikut tiga cara yang umum dipakai:

Cara 1: Ganti Operator > menjadi < #

Pada implementasi hard-coded (non-template), satu-satunya perubahan adalah mengganti > menjadi < pada perbandingan parent vs child. Misalnya pada sift_up:

// max-heap: tukar bila parent lebih kecil dari child
while (i > 0 && data[parent(i)] < data[i]) { ... }
// min-heap: tukar bila parent lebih besar dari child
while (i > 0 && data[parent(i)] > data[i]) { ... }

Cara 2: Gunakan Comparator (seperti kode di atas) #

Pola template dengan Compare memungkinkan satu implementasi melayani kedua varian.

Cara 3: Negasi Nilai untuk “Trik Kasar” #

Untuk tipe numerik, kita dapat menyimpan -v alih-alih v agar max-heap berperilaku seperti min-heap. Trik ini sering dipakai pada soal kompetitif yang melarang custom comparator:

// Heap sebenarnya max-heap, namun karena nilai disimpan sebagai -v,
// elemen terbesar pada -v adalah elemen terkecil pada v.
max_heap.push(-priority);

Kapan Memilih Max-Heap vs Min-Heap #

Pilihan varian ditentukan oleh pertanyaan: operasi apa yang paling sering dilakukan?

• Butuh elemen terbesar dengan cepat, berkali-kali → max-heap. Contoh: scheduling task berprioritas tertinggi, heap sort ascending.
• Butuh elemen terkecil dengan cepat, berkali-kali → min-heap. Contoh: Dijkstra (extract node jarak terkecil), Huffman coding (extract dua node frekuensi terkecil), merge k sorted arrays (extract elemen terkecil berikutnya).

Studi Kasus: Top-k Largest vs Top-k Smallest #

Misalkan kita memiliki stream angka dan ingin mempertahankan k elemen terbesar yang pernah muncul. Strategi yang salah: gunakan max-heap berisi seluruh elemen, lalu ambil k root. Strategi yang benar: gunakan min-heap berukuran k — setiap elemen baru yang lebih besar dari root (elemen ke-k terbesar saat ini) menggantikan root.

Sebaliknya, untuk k elemen terkecil, gunakan max-heap berukuran k. Detail teknis dibahas pada Chapter k-Largest dan k-Smallest.

Verifikasi Sifat Heap-Order #

Kode berikut memverifikasi apakah sebuah array memenuhi sifat max-heap dan min-heap sekaligus, untuk melihat bahwa satu array tidak bisa memenuhi kedua sifat sekaligus (kecuali semua elemen sama):

#include <iostream>
#include <vector>

bool is_max_heap(const std::vector<int>& v) {
    int n = static_cast<int>(v.size());
    for (int i = 1; i < n; ++i) {
        int p = (i - 1) / 2;
        if (v[p] < v[i]) return false;
    }
    return true;
}

bool is_min_heap(const std::vector<int>& v) {
    int n = static_cast<int>(v.size());
    for (int i = 1; i < n; ++i) {
        int p = (i - 1) / 2;
        if (v[p] > v[i]) return false;
    }
    return true;
}

int main() {
    std::vector<int> a = {10, 9, 8, 7, 4, 3, 2, 5, 6, 1};  // max-heap
    std::vector<int> b = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};  // min-heap
    std::vector<int> c = {5, 5, 5, 5, 5};                  // keduanya sekaligus

    std::cout << "a max-heap? " << std::boolalpha << is_max_heap(a)
              << " | min-heap? " << is_min_heap(a) << '\n';
    std::cout << "b max-heap? " << std::boolalpha << is_max_heap(b)
              << " | min-heap? " << is_min_heap(b) << '\n';
    std::cout << "c max-heap? " << std::boolalpha << is_max_heap(c)
              << " | min-heap? " << is_min_heap(c) << '\n';
    return 0;
}

Output yang Dihasilkan:

a max-heap? true | min-heap? false
b max-heap? false | min-heap? true
c max-heap? true | min-heap? true

Bedah Kode Baris-per-Baris #

1. if (v[p] < v[i]) return false; (di is_max_heap): bila ada parent yang lebih kecil dari anak, sifat max-heap dilanggar.
2. if (v[p] > v[i]) return false; (di is_min_heap): kebalikannya untuk min-heap.
3. Array a [10, 9, 8, ...]: max-heap valid (root = 10 = maksimum), tetapi min-heap tidak (10 lebih besar dari anak-anaknya).
4. Array b [1, 2, 3, ...]: min-heap valid, max-heap tidak.
5. Array c [5, 5, 5, 5, 5]: memenuhi kedua sifat sekaligus karena semua elemen sama — parent ≥ child dan parent ≤ child keduanya true saat nilainya sama.

Implementasi STL: std::less dan std::greater #

STL menyediakan dua functor perbandingan standar:

• std::less<T> — mengembalikan a < b. Digunakan untuk max-heap (default std::priority_queue).
• std::greater<T> — mengembalikan a > b. Digunakan untuk min-heap.

Kedua functor ini adalah empty struct dengan operator() — kompiler modern mengoptimalkan instansiasi menjadi inline call tanpa overhead pemanggilan fungsi. Inilah mengapa template comparator pada kode di atas tidak lebih lambat daripada if-else hard-coded.

Ringkasan #

• Max-heap: parent ≥ child, root = elemen maksimum. Cocok untuk heap sort, scheduling prioritas tertinggi.
• Min-heap: parent ≤ child, root = elemen minimum. Cocok untuk Dijkstra, Huffman, merge k sorted arrays.
• Implementasi max-heap dan min-heap identik — perbedaannya hanya operator perbandingan.
• Pola template C++ dengan Compare menyatukan kedua varian dalam satu class.
• std::less = max-heap, std::greater = min-heap — default std::priority_queue STL.
• Array dengan semua elemen sama memenuhi kedua sifat sekaligus (kasus degenerate).

Pada Chapter berikutnya kita akan mengimplementasikan tiga operasi inti heap — insert, extract, dan peek — dengan kompleksitas masing-masing O(log n), O(log n), dan O(1).