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 celah kosong), kita tidak perlu menggunakan pointer seperti pada materi pohon biner sebelumnya. Kita bisa menggunakan Array (Larik) 1 dimensi secara langsung.

Kita bisa mengetahui siapa orang tua dan anak dari suatu elemen di indeks i hanya menggunakan rumus matematika sederhana:

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

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, masukkan data tersebut ke posisi paling akhir (antrean.data[antrean.size]). Kemudian, lakukan evaluasi "naik pangkat":

• Bandingkan data baru dengan orang tuanya.
• Jika data baru lebih besar, tukar posisi.
• Ulangi terus sampai data tersebut lebih kecil dari orang tuanya atau sudah mencapai puncak (indeks 0).

2. Menghapus Data (Heapify)

Dalam Antrean Prioritas, yang dihapus selalu data di puncak (prioritas tertinggi). Caranya:

1. Ambil elemen di posisi terakhir, lalu pindahkan ke posisi puncak yang kosong.
2. Karena puncak sekarang diisi oleh elemen kecil, ia harus "turun pangkat" melalui proses Heapify.

Heapify adalah algoritma untuk memulihkan susunan Heap:

1. Bandingkan simpul puncak dengan kedua anaknya.
2. Cari siapa yang nilainya paling besar di antara mereka bertiga.
3. Jika yang terbesar adalah salah satu anak, tukar posisi.
4. Panggil kembali fungsi Heapify untuk posisi baru tersebut sampai struktur kembali benar.

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