Konsep Heap

Heap adalah struktur data berbentuk complete binary tree yang memenuhi sifat heap-order: setiap node memiliki hubungan tertentu dengan anak-anaknya — pada max-heap parent selalu lebih besar atau sama dengan anak-anaknya, sedangkan pada min-heap parent selalu lebih kecil atau sama dengan anak-anaknya. Berkat sifat complete binary tree tersebut, heap dapat direpresentasikan sebagai array tanpa pointer — posisi parent dan anak dihitung lewat operasi aritmetika sederhana. Pada Chapter ini kita akan membedah dua sifat dasar heap (complete tree dan heap-order), memetakan node-tree ke indeks array, dan memahami mengapa array menjadi representasi paling efisien untuk heap. Pada akhir chapter kita akan punya pondasi yang sama digunakan oleh semua chapter berikutnya di Section ini.

Dua Sifat Fundamental Heap #

Sebuah struktur data disebut heap bila dan hanya jika memenuhi dua sifat berikut:

1. Complete binary tree — semua level pohon terisi penuh kecuali mungkin level terakhir, dan level terakhir terisi dari kiri ke kanan tanpa celah.
2. Heap-order property — pada max-heap v[parent] ≥ v[child], pada min-heap v[parent] ≤ v[child] untuk setiap node.

Complete Binary Tree: Mengapa Tanpa Pointer #

Pada complete binary tree, seluruh node pada level 0..h-1 selalu berjumlah 2^h - 1 (penuh), dan level h diisi dari kiri ke kanan. Karena tidak ada “lubang” di tengah pohon, kita dapat menempatkan seluruh node ke dalam array berurutan menggunakan indeks level-order:

• Root berada pada indeks 0.
• Anak kiri node i: 2i + 1.
• Anak kanan node i: 2i + 2.
• Parent node i: (i - 1) / 2 (pembagian bulat ke bawah).

Tidak ada pointer atau edge eksplisit — relasi parent-anak dihitung on-the-fly lewat indeks aritmetika.

Heap-Order: Bandingkan Parent dengan Anak #

Heap-order hanya membandingkan parent dengan anak. Sibling kiri dan kanan tidak harus terurut. Pada max-heap [10, 9, 8, ...], indeks 1 bernilai 9 dan indeks 2 bernilai 8 — sibling boleh kiri lebih besar atau kanan lebih besar, yang penting keduanya ≤ 10.

Pemetaan Tree ↔ Array #

Misalkan array [10, 9, 8, 7, 4, 3, 2, 5, 6, 1] adalah heap valid. Mari kita petaan ke struktur pohon:

Pohon di atas dibaca dari kiri ke kanan per level: level 0 berisi [10], level 1 berisi [9, 8], level 2 berisi [7, 4, 3, 2], level 3 berisi [5, 6, 1]. Karena pohon complete, tidak ada indeks yang “lompat” — indeks 7..9 adalah anak-anak dari node level 2, terisi dari kiri ke kanan.

Kode: Verifikasi Relasi Indeks #

Kode berikut menampilkan struktur tree yang dihasilkan dari array, lalu memverifikasi rumus parent, left, dan right untuk satu node contoh:

#include <iostream>
#include <vector>

// Menampilkan peta indeks array <-> posisi node pada complete binary tree
int parent(int i) { return (i - 1) / 2; }
int left(int i)   { return 2 * i + 1; }
int right(int i)  { return 2 * i + 2; }

void tampilkan_pohon_dari_array(const std::vector<int>& v) {
    int n = static_cast<int>(v.size());
    int level = 0;
    int idx = 0;
    while (idx < n) {
        int count = 1 << level;             // jumlah node pada level ini
        for (int k = 0; k < count && idx < n; ++k, ++idx) {
            std::cout << v[idx] << ' ';
        }
        std::cout << '\n';
        ++level;
    }
}

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

    std::cout << "Array        : ";
    for (int x : heap) std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "Struktur tree (per level):\n";
    tampilkan_pohon_dari_array(heap);

    std::cout << "\nRelasi indeks (untuk elemen 8 pada indeks 2):\n";
    int i = 2;
    std::cout << "parent(" << i << ")      = " << parent(i) << " -> nilai " << heap[parent(i)] << '\n';
    std::cout << "left_child(" << i << ")  = " << left(i)   << " -> nilai " << heap[left(i)]   << '\n';
    std::cout << "right_child(" << i << ") = " << right(i)  << " -> nilai " << heap[right(i)]  << '\n';

    return 0;
}

Output yang Dihasilkan:

Array        : 10 9 8 7 4 3 2 5 6 1 
Struktur tree (per level):
10 
9 8 
7 4 3 2 
5 6 1 

Relasi indeks (untuk elemen 8 pada indeks 2):
parent(2)      = 0 -> nilai 10
left_child(2)  = 5 -> nilai 3
right_child(2) = 6 -> nilai 2

Bedah Kode Baris-per-Baris #

1. int parent(int i) { return (i - 1) / 2; }: untuk indeks i > 0, parent selalu berada pada (i - 1) / 2 (pembagian bulat ke bawah untuk bilangan bulat positif). Root (i = 0) tidak punya parent — (0 - 1) / 2 = -1 / 2 = 0 (karena pembagian bulat C++ ke arah nol), sehingga rumus “aman” dipanggil untuk root sekalipun, namun hasilnya tetap 0 (root sendiri).
2. int left(int i) { return 2 * i + 1; }: anak kiri dari node i selalu berada pada 2i + 1. Indeks ini bisa melebihi ukuran array jika i adalah daun — pemanggil harus mengecek batas.
3. int right(int i) { return 2 * i + 2; }: anak kanan pada 2i + 2.
4. int count = 1 << level;: jumlah maksimum node pada level tertentu adalah 2^level. Pada level 0 ada 1 node, level 1 ada 2, level 2 ada 4, dan seterusnya.
5. for (int k = 0; k < count && idx < n; ++k, ++idx): cetak node sebanyak count atau hingga array habis (idx < n). Iterasi berhenti lebih awal pada level terakhir yang belum penuh.
6. Output struktur tree: terlihat bahwa array [10, 9, 8, 7, 4, 3, 2, 5, 6, 1] benar-benar membentuk pohon complete binary tree — level 3 hanya punya 3 node (5 6 1) padahal idealnya 8, sesuai dengan n = 10 total node.
7. Verifikasi relasi: untuk node indeks 2 (nilai 8), parent di indeks 0 (nilai 10) — memenuhi 10 ≥ 8. Anak kiri di indeks 5 (nilai 3) dan anak kanan di indeks 6 (nilai 2) — keduanya lebih kecil dari 8. Heap-order max-heap terpenuhi.

Mengapa Array Lebih Efisien dari Pointer #

Pada representasi pointer-based binary tree, setiap node menyimpan tiga hal: nilai, pointer ke anak kiri, dan pointer ke anak kanan. Untuk heap berisi n elemen, struktur tersebut menghabiskan 3n memori (nilai + 2 pointer) dan menyebarkan node di seluruh heap memori proses.

Representasi array menghabiskan tepat n slot memori yang berdekatan (contiguous). Hasilnya:

Tinggi Heap: O(log n) #

Tinggi heap berisi n elemen adalah ⌊log₂ n⌋. Alasannya: level 0..h-1 selalu penuh berisi 2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1 node. Level h paling banyak berisi 2^h node lagi. Karena 2^h - 1 < n ≤ 2^(h+1) - 1, kita peroleh h = ⌊log₂ n⌋.

Konsekuensi: setiap operasi yang menelusuri jalur root-ke-daun (insert, extract-max, heapify pada satu node) berbiaya O(log n) karena jalurnya sepanjang tinggi pohon.

Verifikasi Heap-Order dengan Loop #

Mari kita periksa apakah array [10, 9, 8, 7, 4, 3, 2, 5, 6, 1] benar-benar memenuhi sifat max-heap, lalu bandingkan dengan array yang tidak memenuhi:

#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;     // parent lebih kecil → bukan max-heap
    }
    return true;
}

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

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

Output yang Dihasilkan:

a adalah max-heap? true
b adalah max-heap? false

Bedah Kode Baris-per-Baris #

1. for (int i = 1; i < n; ++i): iterasi dari indeks 1 (anak pertama) hingga akhir. Root (indeks 0) tidak punya parent, jadi mulai dari 1.
2. int p = (i - 1) / 2;: indeks parent dari node i.
3. if (v[p] < v[i]) return false;: bila ada parent yang lebih kecil dari anaknya, sifat max-heap dilanggar. Segera kembalikan false.
4. b gagal: pada array b, root bernilai 1 namun indeks 9 bernilai 10 — parent indeks 9 adalah (9-1)/2 = 4 yang bernilai 4. Karena 4 < 10, max-heap dilanggar.

Ringkasan #

• Heap adalah complete binary tree yang memenuhi heap-order: parent ≥ child (max-heap) atau parent ≤ child (min-heap).
• Complete binary tree memungkinkan representasi array tanpa pointer: anak kiri 2i+1, anak kanan 2i+2, parent (i-1)/2.
• Tinggi heap adalah ⌊log₂ n⌋ — semua operasi jalur root-daun berbiaya O(log n).
• Array-based heap lebih efisien daripada pointer-based: memori O(n) (tanpa overhead pointer) dan cache-friendly.
• Heap-order hanya membandingkan parent dengan anak, bukan sibling kiri vs kanan.

Pada Chapter berikutnya kita akan membedah dua varian heap — min-heap dan max-heap — dan melihat bagaimana memilih varian yang tepat untuk setiap skenario.