Konsep heap

Heap adalah struktur data pohon yang menyimpan kumpulan nilai dengan satu janji sederhana, yaitu elemen terkecil atau terbesar selalu menempati akarnya. Topik ini membedah bentuk pohon biner lengkap yang menjadi fondasi heap, invarian yang membedakan min-heap dari max-heap, serta pemetaan pohon ke dalam array yang membuat heap sangat hemat memori. Demonstrasi dilakukan dengan membangun heap dari array sembarang, lalu membaca kembali strukturnya lewat array dan daftar per level. Setelah selesai membaca, invarian sebuah heap dapat diperiksa langsung dari isi arraynya.

Pohon biner lengkap#

Heap dibangun di atas pohon biner lengkap (complete binary tree), yaitu pohon yang setiap levelnya penuh kecuali mungkin level terakhir, dan level terakhir itu terisi dari kiri ke kanan tanpa celah. Bentuk ini terlihat sepele, tetapi akibatnya besar karena tinggi pohon terkunci di sekitar $\lfloor \log_2 n \rfloor$ untuk $n$ simpul. Pohon biner biasa boleh tumbuh melengkung seperti rantai satu simpul per level sehingga tingginya mencapai $n$, sedangkan pohon lengkap dipaksa gemuk dan pendek. Setiap operasi yang bergerak dari akar ke daun, seperti push dan pop yang dibedah pada topik operasi heap, selesai paling lama sepanjang tinggi pohon itu.

Kekosongan yang dilarang hanyalah celah di tengah level, bukan daun yang memang belum ada. Pohon tujuh simpul yang dipakai di topik ini terisi penuh pada dua level pertama, sedangkan pohon enam simpul akan meninggalkan satu anak kanan kosong di dasar dan tetap sah sebagai pohon lengkap. Karena tidak ada lubang dan setiap simpul selain akar punya tepat satu induk, keseluruhan bentuk cukup dinyatakan dengan satu angka $n$ tanpa atribut tambahan. Properti inilah yang nantinya dipakai untuk menjorokkan seluruh pohon ke dalam satu array polos.

Invarian min-heap dan max-heap#

Invarian (invariant) heap adalah aturan nilai yang dipertahankan di setiap pasangan induk dan anak, bukan kebetulan susunan data. Pada min-heap, nilai setiap simpul tidak boleh lebih besar dari nilai anak-anaknya, sehingga simpul terkecil otomatis berada di akar. Max-heap memakai kebalikannya, yaitu setiap induk tidak boleh lebih kecil dari anak-anaknya, sehingga akar menyimpan nilai terbesar. Selain aturan nilainya, kedua varian itu identik, termasuk bentuk pohon lengkap dan cara representasinya.

Invarian heap bersifat hierarkis dan lemah, bukan urutan global. Dua simpul bersaudara tidak punya janji urutan apa pun, dan seluruh subpohon kanan boleh berisi nilai yang lebih kecil daripada simpul mana pun di subpohon kiri. Perilaku ini membedakan heap dari binary search tree yang menuntut kiri lebih kecil dari induk dan kanan lebih besar, sehingga penelusuran tertentu menghasilkan urutan naik. Pada heap, membaca isi array dari depan ke belakang tidak menghasilkan urutan naik maupun turun, hanya memenuhi janji antara induk dan anak.

Konsekuensi invarian yang lemah tersebut: heap bukan alat untuk mencari nilai sembarang, karena pencariannya tetap $O(n)$. Heap adalah alat untuk menjawab pertanyaan “yang paling ekstrem” dengan cepat, baik minimum pada min-heap maupun maksimum pada max-heap. Pertanyaan semacam itu muncul di banyak tempat, dari seleksi k nilai terbesar sampai penjadwalan tugas.

Representasi dalam array#

Bentuk lengkap membuat pointer tidak diperlukan sama sekali. Seluruh pohon cukup dijejalkan ke dalam array mengikuti urutan level, dengan akar di indeks 0 dan setiap level diisi berurutan dari kiri. Rumusnya tetap dan berlaku di semua bahasa yang menghitung indeks dari 0, yaitu anak kiri berada di $2i+1$, anak kanan di $2i+2$, dan induk dari indeks $i$ di $\lfloor (i-1)/2 \rfloor$. Tidak ada byte yang terbuang untuk pointer, dan setiap lompatan pohon menjadi operasi aritmetika indeks.

Diagram berikut memetakan satu min-heap berisi tujuh nilai ke dalam arraynya. Setiap simpul pohon memiliki warna yang sama dengan sel array tempat nilainya tersimpan, sedangkan label $2i+1$ dan $2i+2$ menunjukkan rumus indeks anak pada dua garis turunan dari akar.

Pembacaan arah sebaliknya juga penting. Induk terakhir yang masih memiliki anak berada di $\lfloor n/2 \rfloor - 1$, sedangkan indeks $\lfloor n/2 \rfloor$ sampai $n-1$ pasti berupa daun. Batas ini bukan sekadar pengetahuan, melainkan titik awal proses pembangunan heap, karena simpul tanpa anak tidak perlu diturunkan ke mana pun.

Membangun heap dari array sembarang#

Array sembarang diubah menjadi heap dengan proses yang disebut heapify, yaitu sift down pada setiap induk mulai dari $\lfloor n/2 \rfloor - 1$ mundur sampai akar. Mekanisme tukar-menukar sift down sendiri dibedah tuntas pada topik operasi heap, sedangkan topik ini memakainya sebagai alat penyusun. Program berikut menyusun array [9, 4, 7, 1, 3, 6, 2] menjadi min-heap, lalu mencetak hasilnya sebagai array, sebagai daftar per level, dan sebagai peta rumus indeks.

"""Membangun min-heap dari array tetap, lalu membaca peta indeksnya."""

data = [9, 4, 7, 1, 3, 6, 2]   # array awal, belum memenuhi invarian heap


def sift_down(arr, i, n):
    """Turunkan elemen di indeks i dengan menukarnya pada anak terkecilnya."""
    while True:
        terkecil = i
        kiri, kanan = 2 * i + 1, 2 * i + 2
        if kiri < n and arr[kiri] < arr[terkecil]:
            terkecil = kiri
        if kanan < n and arr[kanan] < arr[terkecil]:
            terkecil = kanan
        if terkecil == i:
            return
        arr[i], arr[terkecil] = arr[terkecil], arr[i]
        i = terkecil


n = len(data)

# heapify: sift down dari induk terakhir pada indeks n//2 - 1 menuju akar
for i in range(n // 2 - 1, -1, -1):
    sift_down(data, i, n)

print("array heap :", data)

# gambaran per level: akar di level 0, dua anak di level 1, dan seterusnya
mulai, ukuran, level = 0, 1, 0
while mulai < n:
    akhir = min(mulai + ukuran, n)
    print(f"level {level}    : {data[mulai:akhir]}")
    mulai, ukuran, level = akhir, ukuran * 2, level + 1

print()

# peta indeks: anak kiri 2i+1, anak kanan 2i+2, induk (i-1)//2
for i in range(n // 2):
    kiri, kanan = 2 * i + 1, 2 * i + 2
    baris = f"induk i={i} (nilai {data[i]}) -> anak kiri i={kiri} (nilai {data[kiri]})"
    if kanan < n:
        baris += f", anak kanan i={kanan} (nilai {data[kanan]})"
    print(baris)

array heap : [1, 3, 2, 4, 9, 6, 7]
level 0    : [1]
level 1    : [3, 2]
level 2    : [4, 9, 6, 7]

induk i=0 (nilai 1) -> anak kiri i=1 (nilai 3), anak kanan i=2 (nilai 2)
induk i=1 (nilai 3) -> anak kiri i=3 (nilai 4), anak kanan i=4 (nilai 9)
induk i=2 (nilai 2) -> anak kiri i=5 (nilai 6), anak kanan i=6 (nilai 7)

Bandingkan keluaran dengan diagram sebelumnya, keduanya menampilkan heap yang sama, yaitu [1, 3, 2, 4, 9, 6, 7]. Baris per level memperlihatkan bentuk pohonnya, satu nilai di akar, dua anak di level berikutnya, lalu empat daun di dasar. Tiga baris terakhir adalah peta rumus indeksnya, misalnya induk di indeks 1 bernilai 3 dengan anak kiri di $2 \times 1 + 1 = 3$ bernilai 4 dan anak kanan di $2 \times 1 + 2 = 4$ bernilai 9. Invarian terbaca langsung dari keluaran, tidak ada induk yang lebih besar dari anak-anaknya.

Kesalahan umum#

1. Membaca array heap seolah sudah terurut. Array [1, 3, 2, 4, 9, 6, 7] memenuhi invarian min-heap padahal deretannya tidak naik. Kebiasaan yang benar adalah memeriksa setiap induk terhadap anak-anaknya, atau melakukan pop berulang bila urutan terurut memang dibutuhkan.
2. Mencampur rumus indeks berbasis 0 dan berbasis 1. Rumus $2i+1$ dan $2i+2$ hanya sah untuk indeks yang dihitung dari 0, sedangkan sebagian buku memakai rumus $2i$ dan $2i+1$ pada penomoran berbasis 1. Menjalankan satu rumus pada konvensi yang lain menghasilkan indeks yang selalu bergeser, dan invarian heap pun rusak tanpa penyebab yang jelas.
3. Mengira setiap pohon lengkap otomatis menjadi heap. Bentuk lengkap hanya mengatur letak simpul, sedangkan invarian mengatur nilainya. Pohon lengkap yang akarnya paling besar tetap bukan min-heap, sehingga bentuk dan invarian diperiksa terpisah.
4. Mengurutkan data terlebih dahulu hanya untuk membangun heap. Pengurutan penuh membangun heap dalam $O(n \log n)$, sedangkan heapify langsung pada array sembarang hanya $O(n)$. Cara yang lebih mahal itu juga tidak perlu, karena heap tidak pernah menuntut urutan global antarelemen.

Ringkasan#

• Heap dibangun di atas pohon biner lengkap, sehingga tingginya sekitar $\lfloor \log_2 n \rfloor$ dan seluruh isinya cukup disimpan dalam satu array tanpa pointer.
• Rumus indeksnya tetap: anak kiri $2i+1$, anak kanan $2i+2$, dan induk $\lfloor (i-1)/2 \rfloor$, dengan daun mulai indeks $\lfloor n/2 \rfloor$.
• Min-heap menjamin induk tidak lebih besar dari anak-anaknya, max-heap menjamin kebalikannya, dan akar selalu menyimpan nilai ekstrem.
• Invarian heap bersifat hierarki lemah, sehingga isi array heap bukan deretan terurut.

Referensi#

• heapq — Heap queue algorithm — Python Software Foundation — dokumentasi heapq yang merumuskan invarian min-heap serta relasi induk dan anak pada array.
• Heap (data structure) — Wikipedia — definisi heap, sifat pohon lengkap, dan representasinya dalam array.