Operasi Heap

Tiga operasi inti yang membuat heap berguna adalah peek (melihat elemen prioritas tertinggi), insert (menambah elemen baru), dan extract (mengeluarkan elemen prioritas tertinggi). Kompleksitas ketiganya tidak simetris: peek O(1) karena elemen selalu di root, sedangkan insert dan extract O(log n) karena harus menjaga heap-order lewat operasi sift up dan sift down. Pada Chapter ini kita akan membedah mekanisme kedua operasi tersebut, mengimplementasikan class heap generik berbasis template C++ yang lengkap, dan menjelaskan baris-per-baris implementasi sift up dan sift down. Pada akhir chapter kita akan punya implementasi heap yang siap dipakai untuk masalah-masalah lanjutan seperti Dijkstra atau k-Largest.

Tiga Operasi Inti Heap #

Operasi	Kompleksitas	Mekanisme
`peek` / `top`	`O(1)`	Akses elemen indeks 0
`insert` / `push`	`O(log n)`	Tambah di akhir array, lalu sift up
`extract` / `pop`	`O(log n)`	Simpan root, pindahkan elemen terakhir ke root, sift down

Operasi peek adalah yang termurah — root selalu berada pada indeks 0, tidak perlu penelusuran apa pun. Operasi insert dan extract harus menjaga heap-order yang bisa saja dilanggar setelah modifikasi, sehingga memerlukan sift untuk merestorasi struktur.

Insert: Sift Up ke Atas #

Aturan #

push(v) menambahkan elemen baru v ke heap. Setelah penambahan, heap-order mungkin dilanggar karena v bisa lebih besar (pada max-heap) dari parent-nya. Operasi sift up mengembalikan heap-order dengan menukar v dengan parent selama v lebih besar dari parent.

Mekanisme Sift Up #

flowchart TD A["Push 10"] --> B["append di akhir array: [4, 5, 3, 10]"] B --> C{"parent(3) = idx 1 data[1] = 5 10 > 5?"} C -- Ya --> D["swap array: [4, 10, 3, 5]"] D --> E{"parent(1) = idx 0 data[0] = 4 10 > 4?"} E -- Ya --> F["swap array: [10, 4, 3, 5]"] F --> G{"i = 0 (root), stop"}

Setelah sift up selesai, elemen 10 yang baru di-push berakhir di root karena merupakan nilai terbesar. Heap-order kembali terpenuhi.

Extract: Sift Down ke Bawah #

Aturan #

pop() mengeluarkan elemen prioritas tertinggi (root). Untuk menghindari gap pada root, kita memindahkan elemen terakhir array ke root, lalu menjalankan sift down dari root agar heap-order pulih.

Mekanisme Sift Down #

flowchart TD A["Heap awal: [10, 5, 8, 3, 4]"] --> B["Simpan root (10)"] B --> C["Pindahkan elemen terakhir ke root [4, 5, 8, 3]"] C --> D{"Anak: left=5, right=8 8 > 5, swap dengan kanan"} D --> E["[8, 5, 4, 3]"] E --> F{"Node idx 2 (4): anak tidak ada stop"} F --> G["Return 10"]

Setelah sift down selesai, elemen 4 yang dipindahkan ke root berakhir pada posisi yang sesuai — di antara anak-anaknya yang lebih besar. Heap-order pulih, root kini berisi 8 (elemen kedua terbesar).

Kode: Class Heap Lengkap #

Berikut implementasi lengkap heap generik berbasis template C++ dengan ketiga operasi inti:

cpp
#include <iostream>
#include <vector>
#include <functional>
#include <stdexcept>

template <typename T, typename Compare = std::less<T>>
class Heap {
    std::vector<T> data;
    Compare cmp;

    int parent(int i) const { return (i - 1) / 2; }
    int left(int i)   const { return 2 * i + 1; }
    int right(int i)  const { return 2 * i + 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);
        }
    }

    void sift_down(int i) {
        int n = static_cast<int>(data.size());
        while (true) {
            int l = left(i), r = right(i), best = i;
            if (l < n && cmp(data[best], data[l])) best = l;
            if (r < n && cmp(data[best], data[r])) best = r;
            if (best == i) break;
            std::swap(data[i], data[best]);
            i = best;
        }
    }

public:
    bool empty() const { return data.empty(); }
    std::size_t size() const { return data.size(); }
    const T& top() const {
        if (data.empty()) throw std::out_of_range("heap kosong");
        return data.front();
    }

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

    T pop() {
        if (data.empty()) throw std::out_of_range("heap kosong");
        T result = data.front();
        data.front() = data.back();
        data.pop_back();
        if (!data.empty()) sift_down(0);
        return result;
    }
};

int main() {
    Heap<int, std::less<int>> h;  // max-heap

    std::cout << "Push 4, 10, 3, 5, 1\n";
    for (int x : {4, 10, 3, 5, 1}) {
        h.push(x);
        std::cout << "  top = " << h.top() << " (size=" << h.size() << ")\n";
    }

    std::cout << "\nPop semua (urutan descending):\n";
    while (!h.empty()) {
        std::cout << ' ' << h.pop();
    }
    std::cout << '\n';

    std::cout << "\nCoba pop dari heap kosong:\n";
    try {
        h.pop();
    } catch (const std::exception& e) {
        std::cout << "exception: " << e.what() << '\n';
    }

    return 0;
}

Output yang Dihasilkan:

text
Push 4, 10, 3, 5, 1
  top = 4 (size=1)
  top = 10 (size=2)
  top = 10 (size=3)
  top = 10 (size=4)
  top = 10 (size=5)

Pop semua (urutan descending):
 10 5 4 3 1

Coba pop dari heap kosong:
exception: heap kosong

Bedah Kode Baris-per-Baris #

template <typename T, typename Compare = std::less<T>>: default comparator std::less menjadikan class ini default max-heap. Pengguna bisa override dengan std::greater untuk min-heap.
void sift_up(int i): sift up dari indeks i. Kondisi loop i > 0 && cmp(data[parent(i)], data[i]) — true bila masih ada parent (i > 0) dan parent harus ditukar dengan child. Untuk max-heap (std::less), cmp(parent, child) adalah parent < child — true bila parent lebih kecil, sehingga swap.
std::swap(data[parent(i)], data[i]); i = parent(i);: tukar parent dengan child, lalu pindahkan pointer i ke posisi parent agar iterasi berikutnya mengecek parent berikutnya.
void sift_down(int i): sift down dari indeks i. Mencari anak terbesar (untuk max-heap) dan menukar dengan parent bila anak lebih besar.
int l = left(i), r = right(i), best = i;: hitung indeks anak kiri, anak kanan, dan asumsikan i sendiri adalah yang terbaik. Variabel best akan diperbarui bila anak kiri atau kanan lebih layak naik.
if (l < n && cmp(data[best], data[l])) best = l;: bila anak kiri ada dan lebih layak (untuk max-heap: lebih besar), perbarui best. Perhatikan perbandingan dengan best, bukan dengan i — ini memastikan kita memilih anak terbesar di antara kedua anak.
if (r < n && cmp(data[best], data[r])) best = r;: bandingkan dengan anak kanan juga.
if (best == i) break;: bila i sendiri yang terbaik, heap-order sudah pulih — berhenti.
std::swap(data[i], data[best]); i = best;: tukar dengan anak terbesar, lanjutkan sift down dari posisi anak tersebut.
void push(const T& v): tambah elemen ke akhir vector (O(1) amortized), lalu sift up dari indeks terakhir (data.size() - 1).
T pop(): kembalikan root, lalu pindahkan elemen terakhir ke root, hapus elemen terakhir (pop_back), dan sift down dari root. Bila heap menjadi kosong setelah pop_back, sift down dilewati.
Output push: setelah push 4, root = 4. Setelah push 10, sift up menukar 10 ke root → root = 10. Elemen-elemen berikutnya (3, 5, 1) lebih kecil dari 10 sehingga root tetap 10.
Output pop: pertama kembalikan 10, lalu 5, 4, 3, 1 — urutan descending. Inilah dasar dari heap sort: pop berulang menghasilkan elemen terurut.
Exception handling: pop pada heap kosong melempar std::out_of_range dengan pesan "heap kosong". Tanpa proteksi ini, akses data.front() pada vector kosong adalah undefined behavior.

Mengapa Pop Memindahkan Elemen Terakhir ke Root #

Bila kita menghapus root dan menggeser seluruh elemen ke kiri (seperti queue), struktur complete binary tree akan rusak — ada “lubang” pada root. Strategi yang lebih murah: ambil elemen terakhir array (satu-satunya yang boleh dihapus tanpa merusak complete tree), pindahkan ke root, lalu sift down.

Konsekuensi: kompleksitas pop adalah O(log n) (sift down sepanjang tinggi pohon), bukan O(n) (geser seluruh elemen). Strategi ini juga membuat pop in-place — tidak ada alokasi memori tambahan.

Kompleksitas Operasi #

Operasi	Best Case	Worst Case	Amortized
`push`	`O(1)` (elemen baru tetap di tempat)	`O(log n)` (sampai root)	`O(log n)`
`pop`	`O(1)` (anak-anak lebih besar, tidak ada swap)	`O(log n)` (sampai daun)	`O(log n)`
`top`	`O(1)`	`O(1)`	`O(1)`
`empty`/`size`	`O(1)`	`O(1)`	`O(1)`

Operasi Tambahan: Replace Root #

Beberapa implementasi heap menyediakan operasi replace(v) yang mengganti root dengan nilai baru dan langsung sift down. Operasi ini lebih efisien daripada pop lalu push (1 sift down vs 1 sift up + 1 sift down):

cpp
T replace(const T& v) {
    if (data.empty()) throw std::out_of_range("heap kosong");
    T old = data.front();
    data.front() = v;
    sift_down(0);
    return old;
}

Operasi ini berguna pada k-largest problem (ganti root bila elemen baru lebih besar) dan algoritma median of stream (pertahankan ukuran heap konstan).

Verifikasi Heap-Order Setelah Operasi #

Untuk memastikan implementasi benar, kita dapat menambahkan fungsi check_heap yang memverifikasi sifat heap setelah setiap operasi. Strategi ini sering dipakai saat debugging:

cpp
#include <cassert>
// ...
bool check_heap() const {
    int n = static_cast<int>(data.size());
    for (int i = 1; i < n; ++i) {
        int p = parent(i);
        if (cmp(data[p], data[i])) return false;  // parent < child (untuk max-heap)
    }
    return true;
}

Fungsi check_heap berbiaya O(n) — gunakan hanya pada test, bukan pada kode produksi, karena akan memperlambat operasi push/pop.

Ringkasan #

top (peek) berbiaya O(1) — root selalu di indeks 0.
push berbiaya O(log n) — sift up sepanjang jalur daun-ke-root.
pop berbiaya O(log n) — pindahkan elemen terakhir ke root, lalu sift down sepanjang jalur root-ke-daun.
Pola template Compare menyatukan max-heap dan min-heap dalam satu class.
replace lebih efisien daripada pop + push untuk skenario “ganti root”.
Operasi pop pada heap kosong harus melempar exception — akses vector kosong adalah undefined behavior.

Pada Chapter berikutnya kita akan membahas heapify — operasi membangun heap dari array acak dalam O(n) (bukan O(n log n)), berserta analisis kompleksitasnya.