Heap Sort

Heap sort memanfaatkan struktur binary heap untuk mengurutkan array dalam O(n log n) waktu dan O(1) memori tambahan. Algoritma ini bekerja dalam dua fase: membangun max-heap dari array awal, lalu mengekstrak elemen maksimum satu per satu hingga array terurut. Heap sort in-place dan menjamin O(n log n) pada semua kasus — best, average, worst. Pada Chapter ini kita akan membedah mekanisme heapify, mengimplementasikan heap sort, dan menjelaskan mengapa algoritma ini tidak stabil. Pada akhir chapter kita akan paham kapan heap sort menjadi pilihan utama: ketika dibutuhkan jaminan worst case O(n log n) dengan memori O(1).

Aturan: Build Heap, Extract Max #

Heap sort bekerja dalam dua fase:

1. Build max-heap — susun array sehingga memenuhi sifat max-heap: setiap node lebih besar atau sama dengan anak-anaknya.
2. Extract max berulang — tukar root (elemen maksimum) dengan elemen terakhir, kurangi ukuran heap, lalu perbaiki heap dengan sift down pada root.

Setelah n-1 iterasi extract, array terurut ascending.

Mekanisme Max-Heap #

Pada max-heap berbasis array (representasi level-order):

• Anak kiri node i: 2i + 1.
• Anak kanan node i: 2i + 2.
• Parent node i: (i - 1) / 2.
• Sifat heap: v[parent(i)] >= v[i] untuk semua i (kecuali root).

Array [10, 9, 8, 7, 4, 3, 2, 5, 6, 1] merepresentasikan pohon heap di atas — setiap parent lebih besar dari anak-anaknya.

Kode: Heap Sort #

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

void sift_down(std::vector<int>& v, int idx, int n) {
    while (true) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        int largest = idx;
        if (left < n && v[left] > v[largest]) largest = left;
        if (right < n && v[right] > v[largest]) largest = right;
        if (largest == idx) break;
        std::swap(v[idx], v[largest]);
        idx = largest;
    }
}

void heap_sort(std::vector<int>& v) {
    int n = static_cast<int>(v.size());
    if (n < 2) return;

    // Build max-heap
    for (int i = n / 2 - 1; i >= 0; --i) {
        sift_down(v, i, n);
    }
    std::cout << "Max-heap setelah build: ";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';

    // Extract max
    for (int end = n - 1; end > 0; --end) {
        std::swap(v[0], v[end]);
        sift_down(v, 0, end);
    }
}

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {4, 10, 3, 5, 1, 8, 2, 7, 6, 9};
    std::cout << "Sebelum sort: "; print(a);
    heap_sort(a);
    std::cout << "Setelah sort : "; print(a);
    return 0;
}

Output yang Dihasilkan:

Sebelum sort:  4 10 3 5 1 8 2 7 6 9
Max-heap setelah build:  10 9 8 7 4 3 2 5 6 1
Setelah sort :  1 2 3 4 5 6 7 8 9 10

Bedah Kode Baris-per-Baris #

1. void sift_down(std::vector<int>& v, int idx, int n): perbaiki sifat heap pada node idx ke bawah, dengan asumsi sub-heap anak kiri dan kanan sudah memenuhi sifat heap. Parameter n adalah ukuran logis heap.
2. int left = 2 * idx + 1; dan int right = 2 * idx + 2;: indeks anak kiri dan kanan dalam representasi array.
3. int largest = idx;: asumsikan parent adalah yang terbesar.
4. if (left < n && v[left] > v[largest]) largest = left;: bila anak kiri ada dan lebih besar, perbarui largest.
5. if (right < n && v[right] > v[largest]) largest = right;: sama untuk anak kanan. Perhatikan perbandingan dengan largest, bukan dengan idx — ini memastikan kita memilih anak terbesar di antara kedua anak.
6. if (largest == idx) break;: bila parent sudah terbesar, heap valid — berhenti.
7. std::swap(v[idx], v[largest]); idx = largest;: tukar dengan anak terbesar, lanjutkan sift down dari posisi baru.
8. for (int i = n / 2 - 1; i >= 0; --i): loop build heap dari node internal terakhir (n/2 - 1) hingga root. Node dengan indeks ≥ n/2 adalah daun — sudah memenuhi sifat heap by default.
9. for (int end = n - 1; end > 0; --end): loop extract — dari elemen terakhir hingga elemen kedua.
10. std::swap(v[0], v[end]);: tukar root (maksimum) dengan elemen terakhir heap. Elemen terakhir kini berada pada posisi final.
11. sift_down(v, 0, end);: perbaiki heap dengan ukuran end (elemen yang baru ditukar dikecualikan dari heap).
12. Output: array terurut ascending. Max-heap awal [10, 9, 8, 7, 4, 3, 2, 5, 6, 1] sesuai diagram di atas.

Build Max-Heap dalam O(n) #

Walaupun kelihatannya build heap berbiaya O(n log n) (n node × log n per sift_down), analisis lebih cermat menunjukkan kompleksitas O(n). Alasannya: mayoritas node adalah daun (tidak perlu sift down), dan node yang lebih dekat ke root (jarak log n) jumlahnya sedikit.

Analisis Tinggi #

Total kerja build heap:

• n/2 daun — 0 sift step.
• n/4 node level-1 — paling banyak 1 sift step.
• n/8 node level-2 — paling banyak 2 sift step.
• …
• 1 root — paling banyak log n sift step.

Total: n/4 · 1 + n/8 · 2 + n/16 · 3 + ... ≈ n (konvergen ke konstanta).

Kompleksitas #

Heap sort menjamin O(n log n) pada semua kasus — bahkan pada sorted input, reverse sorted, atau random. Inilah keunggulan utamanya dibanding quick sort (yang O(n²) pada worst case).

Mengapa Heap Sort Tidak Stabil #

Pertukaran swap(v[0], v[end]) pada extract max memindahkan elemen terakhir ke root, lalu sift down menggeser elemen-elemen lain. Pertukaran jarak jauh ini dapat merusak urutan relatif elemen equal. Contoh: input {(Budi,5), (Andi,3), (Citra,5)} yang di-sort by key dapat menghasilkan Citra sebelum Budi.

In-Place dan O(1) Memori #

Heap sort in-place dengan O(1) memori tambahan — hanya variabel idx, left, right, largest, end, dan i. Tidak ada alokasi buffer seperti merge sort. Inilah yang membuat heap sort menjadi pilihan untuk lingkungan dengan memori terbatas.

Komparasi: Heap Sort vs Quick Sort vs Merge Sort #

Penggunaan Heap Sort pada Introsort #

std::sort di libstdc++ mengimplementasikan introsort — hybrid yang memantau kedalaman rekursi quick sort. Bila kedalaman melebihi 2·log₂ n, algoritma switch ke heap sort untuk menghindari worst case O(n²). Strategi ini memberikan:

• Rata-rata kecepatan quick sort (cache-friendly).
• Jaminan worst case O(n log n) dari heap sort.

Implementasi Alternatif: std::make_heap + std::sort_heap #

STL menyediakan utilitas heap yang langsung memanfaatkan algoritma di atas:

#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());
    std::cout << "Setelah make_heap: ";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';

    std::sort_heap(v.begin(), v.end());
    std::cout << "Setelah sort_heap: ";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

Setelah make_heap:  10 9 8 7 4 3 2 5 6 1
Setelah sort_heap:  1 2 3 4 5 6 7 8 9 10

1. std::make_heap: membangun max-heap dari range. Kompleksitas O(n).
2. std::sort_heap: mengurutkan range yang sudah berupa heap menjadi sorted ascending. Kompleksitas O(n log n).
3. Catatan: std::sort_heap memerlukan input yang sudah berupa heap — memanggilnya pada array biasa menghasilkan output salah.

Aplikasi Heap Sort #

• Memori terbatas — O(1) auxiliary space, cocok untuk embedded systems.
• Worst case terjamin — sistem real-time yang tidak boleh memiliki degradasi performa.
• Priority queue dengan sorted extraction — semua elemen harus diambil dalam urutan terurut.
• Sub-rutin introsort — fallback ketika quick sort memasuki territory O(n²).

Ringkasan #

• Heap sort bekerja dengan build max-heap O(n) lalu extract max berulang O(n log n).
• Kompleksitas terjamin O(n log n) pada semua kasus.
• In-place O(1) memori tambahan.
• Tidak stabil karena pertukaran jarak jauh pada extract dan sift down.
• Lebih lambat di praktik dibanding quick sort karena akses memori tidak cache-friendly.
• Menjadi fallback pada std::sort (introsort) untuk mencegah worst case quick sort.

Pada chapter-chapter berikutnya kita akan beralih ke algoritma sorting non-comparison: counting sort, radix sort, dan bucket sort, yang dapat mencapai O(n) pada kondisi tertentu.