Heap

Motivasi: Antrean Rumah Sakit

Bayangkan Anda berada di ruang gawat darurat (UGD) sebuah rumah sakit. Antrean di sini tidak menggunakan prinsip siapa cepat dia dapat (FIFO). Jika ada pasien yang datang belakangan namun mengalami serangan jantung kritis, ia akan langsung dipanggil pertama kali melewati pasien lain yang hanya menderita batuk ringan.

Sistem yang mempertahankan antrean berdasarkan urutan kepentingan ini disebut Antrean Prioritas (Priority Queue). Di dalam komputer, elemen yang dilayani selalu elemen yang memiliki nilai prioritas terbesar.

Struktur data paling efisien untuk membangun Antrean Prioritas adalah Heap.

Apa itu Heap?

Heap adalah sebuah pohon biner yang mengikuti aturan Pohon Biner Lengkap (Complete Binary Tree). Artinya, pohon terisi penuh pada setiap tingkatnya, kecuali mungkin pada tingkat paling bawah yang harus terisi mampat dari kiri ke kanan.

Ada dua jenis Heap:

1. MaxHeap: Nilai orang tua (parent) selalu lebih besar atau sama dengan anaknya. Hasilnya: Elemen terbesar selalu berada di puncak (Root).
2. MinHeap: Nilai orang tua selalu lebih kecil atau sama dengan anaknya. Hasilnya: Elemen terkecil selalu berada di puncak.

Berikut adalah contoh visualisasi MaxHeap:

Pohon di dalam Array

Karena Heap wajib berbentuk pohon biner lengkap (tidak ada node kosong di tengah-tengah tingkatan), kita tidak perlu repot-repot menggunakan pointer seperti pada materi Pohon Biner sebelumnya. Kita bisa langsung menggunakan Array (Larik) biasa!

Bagaimana caranya? Kita tinggal menyusun datanya dari atas ke bawah, dari kiri ke kanan.

Jika kita meratakan bentuk pohon visual di atas ke dalam barisan Array, bentuknya akan seperti ini:

Ajaibnya, jika Anda sedang melihat angka di sembarang indeks i, Anda bisa menemukan letak keluarga angka tersebut HANYA dengan rumus matematika sederhana:

• Anak Kiri: (2 * i) + 1
• Anak Kanan: (2 * i) + 2
• Orang Tua: (i - 1) / 2 (dibulatkan ke bawah)

Mari kita buktikan! Misalkan kita sedang menunjuk angka 35 (berada di Indeks 1).

• Siapakah Anak Kirinya? Rumusnya (2 * 1) + 1 = 3. Lihat indeks ke-3, isinya 10! Benar.
• Siapakah Anak Kanannya? Rumusnya (2 * 1) + 2 = 4. Lihat indeks ke-4, isinya 20! Benar.
• Siapakah Orang Tuanya? Rumusnya (1 - 1) / 2 = 0. Lihat indeks ke-0, isinya 40! Sangat tepat.

Operasi Dasar MaxHeap

Bagaimana Heap memastikan elemen tertinggi selalu di puncak saat ada data baru masuk atau keluar?

1. Menambahkan Data (Bubble Up)

Saat ada data baru (pasien darurat) yang masuk, tempatkan data tersebut di kursi paling belakang (antrean.data[antrean.size]). Kemudian, data tersebut harus melalui evaluasi "naik pangkat" yang disebut dengan proses Bubble Up:

• Bandingkan data baru tersebut dengan orang tuanya (menggunakan rumus mencari orang tua).
• Jika data baru ternyata lebih besar dari orang tuanya, tukar posisi mereka.
• Ulangi langkah ini terus-menerus (naik ke atas pohon) sampai data tersebut kalah (lebih kecil) dari orang tuanya, atau sampai ia berhasil merebut posisi puncak (Root).

Ilustrasi Kasus: Bayangkan kita ingin memasukkan angka 50 ke dalam MaxHeap kita.

1. 50 masuk ke belakang antrean, yaitu indeks 5 (menjadi anak kiri dari 5).
2. 50 melihat ke atas mencari orang tuanya. Berdasarkan rumus, orang tuanya di indeks 2 (berisi angka 5). Karena 50 > 5, mereka bertukar tempat!
3. Sekarang 50 berada di indeks 2. Ia kembali melihat ke atas. Orang tuanya di indeks 0 (berisi angka 40). Karena 50 > 40, mereka tukar tempat lagi!
4. Angka 50 kini duduk mantap di posisi puncak (Root). Antrean kembali tertib!

2. Menghapus Data (Heapify)

Dalam Antrean Prioritas, pasien yang ditangani lebih dulu selalu yang ada di puncak (Root). Setelah Root dikeluarkan, terjadi kekosongan posisi. Bagaimana mengisinya tanpa merusak bentuk pohon?

1. Ambil elemen di posisi paling belakang (ujung kanan bawah daun), lalu cabut dan duduk-kan di posisi puncak yang kosong.
2. Karena puncak sekarang diisi oleh elemen yang nilainya relatif kecil, ia harus "turun pangkat" melalui proses Heapify.

Heapify adalah algoritma untuk memulihkan aturan MaxHeap dari atas ke bawah:

• Bandingkan simpul yang sedang dievaluasi dengan kedua anaknya.
• Cari siapa yang memiliki nilai paling besar di antara mereka bertiga (Ayah, Anak Kiri, Anak Kanan).
• Jika yang terbesar adalah salah satu anak, tukar posisi ayah dengan anak yang terbesar tersebut.
• Ulangi langkah ini terus ke bawah sampai ia tidak punya anak lagi atau nilainya sudah lebih besar dari kedua anaknya.

Ilustrasi Kasus: Kita kembalikan kondisi antrean ke awal (40, 35, 5, 10, 20). Pasien 40 dipanggil masuk ruang operasi. Posisi puncak (Root) kini kosong!

1. Elemen paling belakang yaitu 20 dicabut dan ditaruh di kursi Root (indeks 0). Susunan sementara: Root=20, Anak Kiri=35, Anak Kanan=5.
2. Proses Heapify dimulai! 20 membandingkan dirinya dengan kedua anaknya (35 dan 5). Siapa yang paling besar? Ya, 35!
3. Terjadi pertukaran: 20 turun "turun pangkat" ke posisi anak kiri, dan 35 naik merebut kursi Root.
4. Sekarang 20 berada di posisi indeks 1. Ia kembali melihat ke bawah, anak kirinya adalah 10 (indeks 3). Karena 20 > 10, ia menang dan berhenti turun. Antrean kembali stabil!

void Heapify(MaxHeap *H, int i) {
    int size = H->size;
    int largest = i;
    int l = leftChild(i);
    int r = rightChild(i);

    // Cek apakah anak kiri lebih besar
    if (l < size && H->data[l] > H->data[largest]) {
        largest = l;
    }
    // Cek apakah anak kanan lebih besar
    if (r < size && H->data[r] > H->data[largest]) {
        largest = r;
    }

    // Jika ada yang lebih besar dari parent, tukar dan lanjut ke bawah
    if (largest != i) {
        Swap(&H->data[i], &H->data[largest]);
        Heapify(H, largest);
    }
}