Heapify

Heapify adalah operasi mengubah array acak menjadi heap valid dalam satu pass. Pendekatan naif melakukan n kali push (masing-masing O(log n)), menghasilkan total O(n log n). Namun, terdapat strategi yang lebih baik: lakukan sift down dari non-leaf terakhir hingga root, dan hasilnya adalah kompleksitas O(n) — bukan O(n log n). Pada Chapter ini kita akan membedah mekanisme heapify linear, membuktikan secara matematis mengapa kompleksitasnya O(n), dan membandingkan performa kedua pendekatan secara empiris. Pada akhir chapter kita akan paham mengapa std::make_heap STL berkompleksitas O(n) dan kapan harus memilih heapify daripada insert berulang.

Dua Strategi Build Heap #

Strategi Naif: Insert Berulang (O(n log n)) #

Pendekatan langsung: mulai dari heap kosong, lakukan push untuk setiap elemen. Setiap push O(log n), sehingga total O(n log n).

heap = []
for x in arr: heap.push(x)

Hasilnya benar, namun tidak optimal — terutama untuk n besar.

Strategi Linear: Sift Down dari Non-Leaf Terakhir (O(n)) #

Pendekatan cerdas: anggap seluruh array sudah ada di tempatnya. Karena daun (indeks n/2 hingga n-1) sudah memenuhi sifat heap by default (tidak punya anak), kita hanya perlu memperbaiki node internal dari non-leaf terakhir (n/2 - 1) mundur hingga root (indeks 0).

for i in [n/2 - 1, 0]: sift_down(i, n)

Strategi ini disebut heapify linear dan berkompleksitas O(n).

Mengapa Mulai dari Non-Leaf Terakhir #

Indeks n/2 - 1 adalah node internal terakhir — semua indeks ≥ n/2 adalah daun (anak kiri 2i + 1 ≥ 2*(n/2) + 1 > n - 1 berada di luar array). Daun tidak perlu sift down karena tidak punya anak untuk dibandingkan.

Dengan memproses node internal secara mundur, ketika kita sift down pada node i, kedua anaknya sudah berada pada subtree yang valid (sebagai heap). Pre-condition ini membuat sift down cukup sekali untuk memperbaiki seluruh subtree.

Kode: Heapify Linear vs Naif #

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

void sift_down(std::vector<int>& v, int i, int n) {
    while (true) {
        int l = 2*i + 1, r = 2*i + 2, best = i;
        if (l < n && v[l] > v[best]) best = l;
        if (r < n && v[r] > v[best]) best = r;
        if (best == i) break;
        std::swap(v[i], v[best]);
        i = best;
    }
}

// Build heap dengan sift_down dari non-leaf terakhir ke root -> O(n)
void heapify_linear(std::vector<int>& v) {
    int n = static_cast<int>(v.size());
    for (int i = n / 2 - 1; i >= 0; --i) {
        sift_down(v, i, n);
    }
}

// Build heap dengan push berulang -> O(n log n)
void heapify_naive(std::vector<int>& v) {
    std::vector<int> tmp;
    tmp.reserve(v.size());
    auto push = [&](int x) {
        tmp.push_back(x);
        int i = static_cast<int>(tmp.size()) - 1;
        while (i > 0) {
            int p = (i - 1) / 2;
            if (tmp[p] >= tmp[i]) break;
            std::swap(tmp[p], tmp[i]);
            i = p;
        }
    };
    for (int x : v) push(x);
    v = std::move(tmp);
}

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;
}

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

    heapify_linear(a);
    std::cout << "Hasil heapify_linear : ";
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
    std::cout << "valid max-heap? " << std::boolalpha << is_max_heap(a) << '\n';

    heapify_naive(b);
    std::cout << "\nHasil heapify_naive  : ";
    for (int x : b) std::cout << x << ' ';
    std::cout << '\n';
    std::cout << "valid max-heap? " << std::boolalpha << is_max_heap(b) << '\n';

    // Benchmark pada array besar
    constexpr int N = 1'000'000;
    std::vector<int> big1(N), big2(N);
    for (int i = 0; i < N; ++i) { big1[i] = i; big2[i] = i; }

    auto t1 = std::chrono::high_resolution_clock::now();
    heapify_linear(big1);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::cout << "\nheapify_linear " << N << " elemen: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count()
              << " ms\n";

    auto t3 = std::chrono::high_resolution_clock::now();
    heapify_naive(big2);
    auto t4 = std::chrono::high_resolution_clock::now();
    std::cout << "heapify_naive  " << N << " elemen: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t4 - t3).count()
              << " ms\n";

    return 0;
}

Output yang Dihasilkan:

Hasil heapify_linear : 10 9 8 7 4 3 2 5 6 1 
valid max-heap? true

Hasil heapify_naive  : 10 9 8 6 7 3 2 4 5 1 
valid max-heap? true

heapify_linear 1000000 elemen: 3 ms
heapify_naive  1000000 elemen: 21 ms

Bedah Kode Baris-per-Baris #

1. void heapify_linear(std::vector<int>& v): lakukan sift down pada setiap node internal, dari indeks n/2 - 1 mundur ke 0. Daun (indeks ≥ n/2) diabaikan — sudah memenuhi heap-order by default.
2. for (int i = n / 2 - 1; i >= 0; --i): iterasi mundur. Saat kita sift down pada node i, anak-anaknya (indeks > i) sudah diproses sehingga subtree bawahnya adalah heap valid. Inilah pre-condition yang membuat sift down bekerja dengan benar.
3. sift_down(v, i, n): sift down pada node i dengan batas ukuran n (heap mencakup indeks 0..n-1).
4. void heapify_naive(std::vector<int>& v): implementasi naive — push setiap elemen ke tmp baru, lalu salin balik ke v. Tiap push sift up sepanjang jalur daun-ke-root.
5. tmp.reserve(v.size()): alokasi kapasitas sekaligus untuk menghindari realokasi berulang. Tanpa reserve, vector::push_back mungkin realokasi O(log n) kali.
6. Output kedua hasil berbeda namun keduanya valid max-heap — is_max_heap mengembalikan true untuk keduanya. Heap-order bersifat longgar; banyak konfigurasi array yang valid.
7. Benchmark N = 1'000'000: heapify_linear 3 ms vs heapify_naive 21 ms — lebih dari 7× lebih cepat. Selisih ini akan semakin besar seiring n bertambah (rasio O(log n) vs O(n)).

Pembuktian Kompleksitas O(n) #

Kelihatannya heapify linear juga O(n log n) — ada n/2 node, masing-masing O(log n) sift down. Namun analisis lebih cermat menunjukkan kompleksitas sebenarnya adalah O(n).

Analisis Berbasis Tinggi #

Pada heap berisi n elemen dengan tinggi h = ⌊log₂ n⌋:

• Jumlah node pada level k (dari root, k = 0): paling banyak 2^k.
• Node pada level k memiliki tinggi sift down maksimum h - k (jarak ke daun terdekat).
• Total kerja: Σ (jumlah node di level k) × (max sift step di level k).

Daun (level h) tidak diproses. Total kerja sift down adalah:

S = Σ_{k=0}^{h-1} 2^k · (h - k)

Misalkan m = h - k, maka k = h - m, dan ketika k dari 0 hingga h-1, m dari h hingga 1:

S = Σ_{m=1}^{h} 2^(h - m) · m
  = 2^h · Σ_{m=1}^{h} m / 2^m

Deret Σ_{m=1}^{∞} m / 2^m = 2 (konvergen, deret geometri tertimbang). Karena jumlah parsial Σ_{m=1}^{h} m / 2^m ≤ 2, maka:

S ≤ 2 · 2^h ≤ 2n

Jadi total kerja ≤ 2n = O(n). Konstanta kecil, bukan O(n log n).

Intuisi: Mayoritas Node Adalah Daun #

Setengah dari seluruh node adalah daun (n/2 node) — tidak perlu sift down. Seperempat node (n/4) berada satu level di atas daun — paling banyak 1 swap. Hanya root yang berpotensi O(log n) swap. Inilah mengapa total kerja konvergen ke O(n).

Sift Down vs Sift Up untuk Heapify #

Terdapat dua pilihan arah iterasi heapify:

Mengapa sift down lebih cepat? Karena sift down memanfaatkan fakta bahwa daun (sebagian besar node) sudah valid — tidak ada kerja untuk mereka. Sift up tidak punya keuntungan serupa — setiap push harus menelusuri jalur sepanjang log n dari daun ke root.

Komparasi Hasil: Banyak Heap Valid #

Pada output di atas, kedua strategi menghasilkan array berbeda namun keduanya valid max-heap. Ini menunjukkan bahwa banyak konfigurasi array yang valid sebagai heap untuk himpunan elemen yang sama. Heap-order bersifat longgar: hanya parent vs child yang dibandingkan, bukan sibling kiri-kanan.

Konsekuensi praktis: ketika kita membandingkan dua implementasi heap, jangan bandingkan array hasilnya secara langsung. Gunakan is_max_heap (atau is_min_heap) untuk memverifikasi validitas, lalu bandingkan performa melalui benchmark.

Menggunakan std::make_heap STL #

STL menyediakan std::make_heap yang berkompleksitas O(n) dengan strategi yang sama:

#include <iostream>
#include <vector>
#include <algorithm>

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

    std::make_heap(v.begin(), v.end());  // max-heap default
    std::cout << "Hasil std::make_heap: ";
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';

    // Untuk min-heap: gunakan std::greater
    std::vector<int> w = {4, 10, 3, 5, 1, 8, 2, 7, 6, 9};
    std::make_heap(w.begin(), w.end(), std::greater<int>{});
    std::cout << "Hasil make_heap min : ";
    for (int x : w) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

Hasil std::make_heap: 10 9 8 7 4 3 2 5 6 1 
Hasil make_heap min : 1 4 2 5 9 8 3 7 6 10 

std::make_heap membangun max-heap secara default (dengan std::less). Untuk min-heap, berikan std::greater sebagai argumen ketiga. Implementasinya menggunakan sift down dari non-leaf terakhir ke root — sama persis strategi heapify linear di atas.

Kompleksitas Build Heap: Tabel Ringkas #

Aplikasi Heapify #

Heapify muncul di banyak tempat:

1. Heap sort — fase pertama adalah heapify sebelum extract-max berulang.
2. Konversi priority queue dari batch data — bila kita sudah punya seluruh elemen di awal, heapify lebih cepat daripada insert satu per satu.
3. std::priority_queue dari range — sejak C++23, konstruktor menerima range dengan O(n) complexity via heapify internal.
4. Median of stream (offline) — bila seluruh stream sudah ada, heapify dua heap lebih cepat daripada memproses satu per satu.

Ringkasan #

• Heapify linear berkompleksitas O(n), bukan O(n log n).
• Strategi: sift down dari non-leaf terakhir (n/2 - 1) mundur ke root. Daun sudah valid secara default.
• Pembuktian kompleksitas: total kerja S ≤ 2n berdasarkan analisis distribusi tinggi node.
• Sift down lebih cepat daripada sift up untuk build heap karena memanfaatkan daun yang sudah valid.
• std::make_heap STL berkompleksitas O(n) dengan strategi yang sama.
• Benchmark empiris: pada n = 1'000'000, heapify linear ~7× lebih cepat dari naive.

Pada Chapter berikutnya kita akan beralih ke standard library — std::priority_queue, container adapter STL yang memanfaatkan heap secara internal.