Operasi heap

Heap yang sudah tersusun tetap harus bisa menerima nilai baru dan melepas nilai terkecilnya. Topik ini membedah dua operasi inti tersebut, yaitu push yang menambahkan elemen dan pop yang mengeluarkan elemen terkecil, beserta proses sift up dan sift down yang memulihkan invarian setelah setiap perubahan. Implementasi min-heap ditulis dari nol pada Python, dicerminkan pada Java, dan dijalankan sungguhan untuk menunjukkan keluarannya. Di akhir topik, biaya $O(\log n)$ per operasi dapat dijelaskan dari tinggi pohonnya, bukan dari hafalan.

Push dan sift up#

Push menambahkan satu nilai dengan cara yang paling murah terlebih dahulu, yaitu menempelkan nilai baru di ujung array, tepat di slot daun kosong pertama menurut urutan level. Penempatan itu selalu menjaga bentuk pohon lengkap, tetapi belum tentu menjaga invarian, sebab nilai baru bisa lebih kecil dari induknya di $\lfloor (i-1)/2 \rfloor$. Proses sift up menyelesaikan sisanya: selama nilai di indeks $i$ lebih kecil dari induknya, keduanya ditukar dan $i$ naik ke posisi induk. Pertukaran berhenti saat induk sudah tidak lebih besar, atau saat akar tercapai.

Contoh konkretnya terjadi pada heap [1, 3, 2, 4, 9, 6, 7] yang menerima push nilai 0. Nilai 0 menempel di indeks 7, lalu naik melewati induk bernilai 4, 3, dan akhirnya 1 sampai menjadi akar baru. Tiga kali pertukaran selesai untuk tujuh simpul, dan angkanya tidak akan pernah melebihi tinggi pohon $\lfloor \log_2 n \rfloor$. Di situlah asal biaya $O(\log n)$ untuk push, karena setiap langkah hanya memeriksa satu induk dan langkahnya paling banyak sepanjang tinggi pohon.

Pop dan sift down#

Pop mengeluarkan nilai terkecil yang memang sudah menunggu di akar, tetapi akar yang kosong harus diisi ulang dengan rapi. Solusinya dua langkah: pindahkan elemen terakhir array ke posisi akar, lalu turunkan elemen itu ke posisi yang sah lewat sift down. Bentuk pohon lengkap tetap terjaga karena yang berpindah adalah elemen paling akhir, sedangkan invarian dipulihkan oleh proses penurunannya.

Sift down membandingkan nilai dengan kedua anaknya, lalu menukarnya dengan anak yang terkecil, bukan sekadar anak kiri. Pilihan terkecil ini wajib, karena menukar dengan anak kiri yang ternyata lebih besar dari anak kanan akan menempatkan nilai besar di atas nilai kecil dan merusak invarian di bawahnya. Diagram berikut memperlihatkan satu langkah sift down pada heap [9, 3, 2], di mana 9 harus ditukar dengan 2 yang berada di anak kanan.

Setiap langkah sift down menurunkan nilai paling sedikit satu level, sehingga proses berhenti paling lambat di daun. Tinggi pohon lengkap adalah $\lfloor \log_2 n \rfloor$, dan di situlah biaya $O(\log n)$ untuk pop berasal. Pasangan push dan pop yang sama-sama logaritmik itulah yang menjadikan heap mesin sederhana untuk mengulang-ulang perintah “ambil yang terkecil”.

Implementasi min-heap dari nol#

Kelas berikut mengumpulkan seluruh mekanisme di atas dalam satu berkas utuh, yaitu push, pop, _sift_up, _sift_down, dan dari_array yang membangun heap lewat sift down dari $\lfloor n/2 \rfloor - 1$ menuju akar. Kedua metode yang berawalan garis bawah adalah alat internal yang hanya dipanggil oleh push, pop, dan dari_array, tanpa pernah diakses dari luar kelas. Bagian demo di bawah kelas menyusun heap dari [9, 4, 7, 1, 3, 6, 2], mendorong dua nilai baru, lalu mengosongkan heap dengan pop berulang.

"""Implementasi min-heap dari nol: push, pop, sift up, sift down, dan heapify."""


class MinHeap:
    """Min-heap berbasis list, dengan akar sebagai elemen terkecil."""

    def __init__(self):
        self.data = []

    def push(self, nilai):
        """Tempelkan nilai di ujung array, lalu angkat sampai posisinya sah."""
        self.data.append(nilai)
        self._sift_up(len(self.data) - 1)

    def pop(self):
        """Keluarkan elemen terkecil, gantikan akar dengan elemen terakhir."""
        if not self.data:
            raise IndexError("pop dari heap kosong")
        terkecil = self.data[0]
        terakhir = self.data.pop()
        if self.data:
            self.data[0] = terakhir
            self._sift_down(0)
        return terkecil

    @classmethod
    def dari_array(cls, arr):
        """Bangun heap dari array sembarang (heapify), tanpa push satu per satu."""
        heap = cls()
        heap.data = list(arr)
        n = len(heap.data)
        for i in range(n // 2 - 1, -1, -1):
            heap._sift_down(i)
        return heap

    def _sift_up(self, i):
        """Tukar nilai dengan induknya selama induk masih lebih besar."""
        while i > 0:
            induk = (i - 1) // 2
            if self.data[i] < self.data[induk]:
                self.data[i], self.data[induk] = self.data[induk], self.data[i]
                i = induk
            else:
                break

    def _sift_down(self, i):
        """Tukar nilai dengan anak TERKECIL selama masih ada anak yang lebih kecil."""
        n = len(self.data)
        while True:
            terkecil = i
            kiri, kanan = 2 * i + 1, 2 * i + 2
            if kiri < n and self.data[kiri] < self.data[terkecil]:
                terkecil = kiri
            if kanan < n and self.data[kanan] < self.data[terkecil]:
                terkecil = kanan
            if terkecil == i:
                return
            self.data[i], self.data[terkecil] = self.data[terkecil], self.data[i]
            i = terkecil


if __name__ == "__main__":
    # bangun heap dari array sembarang dengan heapify
    heap = MinHeap.dari_array([9, 4, 7, 1, 3, 6, 2])
    print("array heap   :", heap.data)

    # push dua nilai baru, posisinya dicari lewat sift up
    heap.push(0)
    heap.push(5)
    print("setelah push :", heap.data)

    # pop sampai kosong menghasilkan nilai urut dari kecil ke besar
    keluar = []
    while heap.data:
        keluar.append(heap.pop())
    print("urutan pop   :", keluar)

array heap   : [1, 3, 2, 4, 9, 6, 7]
setelah push : [0, 1, 2, 3, 9, 6, 7, 4, 5]
urutan pop   : [0, 1, 2, 3, 4, 5, 6, 7, 9]

Keluaran dapat ditelusuri langkah demi langkah. Array heap [1, 3, 2, 4, 9, 6, 7] adalah hasil heapify, sedangkan setelah push memperlihatkan isi internal [0, 1, 2, 3, 9, 6, 7, 4, 5] yang masih memenuhi invarian meski terlihat tidak beraturan. Pop berulang terakhir mengeluarkan [0, 1, 2, 3, 4, 5, 6, 7, 9], urutan naik sempurna, dan mekanisme inilah yang dipakai pengurutan heapsort.

Perhatikan pula biaya pembangunannya. Memanggil push untuk setiap elemen menelan total $O(n \log n)$, sedangkan heapify yang bekerja dari induk terakhir menuju akar hanya $O(n)$, karena sebagian besar simpul tinggal sedikit level di atas daun sehingga kerja turunnya pendek. Selisih itu nyata pada data besar, dan itulah alasan heapq pada topik aplikasi antrian prioritas menyediakan heapify sebagai bangun awal.

Implementasi yang sama pada Java#

Logika min-heap tidak terikat bahasa, sehingga versi Java berikut memakai array int statis plus penghitung n untuk panjang efektifnya. Rumus indeks, kondisi berhenti, dan urutan langkahnya identik dengan versi Python, termasuk pemilihan anak terkecil saat sift down. Nama kelasnya sama dengan nama berkasnya, sehingga cukup dijalankan dengan java DemoMinHeap.java tanpa tahap kompilasi manual.

import java.util.Arrays;

public class DemoMinHeap {
    static int[] data = new int[64];
    static int n = 0;

    static void push(int nilai) {
        data[n] = nilai;      // tempelkan di slot kosong pertama
        siftUp(n);
        n++;
    }

    static int pop() {
        int terkecil = data[0];
        n--;
        data[0] = data[n];    // elemen terakhir naik ke akar
        siftDown(0);
        return terkecil;
    }

    static void siftUp(int i) {
        while (i > 0) {
            int induk = (i - 1) / 2;
            if (data[i] < data[induk]) {
                int tmp = data[i];
                data[i] = data[induk];
                data[induk] = tmp;
                i = induk;
            } else {
                break;
            }
        }
    }

    static void siftDown(int i) {
        while (true) {
            int terkecil = i;
            int kiri = 2 * i + 1;
            int kanan = 2 * i + 2;
            if (kiri < n && data[kiri] < data[terkecil]) terkecil = kiri;
            if (kanan < n && data[kanan] < data[terkecil]) terkecil = kanan;
            if (terkecil == i) return;
            int tmp = data[i];
            data[i] = data[terkecil];
            data[terkecil] = tmp;
            i = terkecil;
        }
    }

    public static void main(String[] args) {
        int[] awal = {9, 4, 7, 1, 3, 6, 2};
        for (int x : awal) {
            data[n++] = x;
        }
        // heapify: sift down dari induk terakhir menuju akar
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(i);
        }
        System.out.println("array heap   : " + Arrays.toString(Arrays.copyOf(data, n)));

        push(0);
        push(5);
        System.out.println("setelah push : " + Arrays.toString(Arrays.copyOf(data, n)));

        StringBuilder urutan = new StringBuilder();
        while (n > 0) {
            urutan.append(pop());
            if (n > 0) {
                urutan.append(", ");
            }
        }
        System.out.println("urutan pop   : [" + urutan + "]");
    }
}

array heap   : [1, 3, 2, 4, 9, 6, 7]
setelah push : [0, 1, 2, 3, 9, 6, 7, 4, 5]
urutan pop   : [0, 1, 2, 3, 4, 5, 6, 7, 9]

Keluarannya sama persis dengan versi Python, satu bukti bahwa heap hanya rumus indeks dan aturan tukar, bukan fitur bahasa tertentu. Kode ini sengaja memakai metode statis dan array primitif int agar fokusnya tetap pada rumus indeks, tanpa perbandingan objek pembungkus Integer. Perulangan pop di akhir merangkai keluaran dengan StringBuilder, karena Java tidak punya pencetakan list serapi print pada Python. Pemanggilan Arrays.copyOf(data, n) mencetak hanya bagian array yang terpakai, karena slot di luarnya masih menyimpan sisa nilai lama. Perbedaan yang tersisa hanya pada pengelolaan kapasitas, karena array int[64] harus digandakan ke array yang lebih besar saat penuh, sedangkan list Python menangani pertumbuhan itu sendiri. Pola penggandaan kapasitas semacam ini sudah dibedah pada modul array ketika membahas array dinamis.

Kesalahan umum#

1. Menukar dengan anak kiri, bukan anak terkecil, saat sift down. Pada heap [9, 3, 2], menukar 9 dengan anak kiri 3 menempatkan 3 di atas 2 sehingga invarian tetap rusak. Perbaikannya sederhana, yaitu membandingkan kedua anak terlebih dahulu, lalu menukar dengan yang terkecil dari keduanya.
2. Melupakan pemindahan elemen terakhir ke akar. Pop yang hanya menghapus data[0] tanpa menaruh elemen terakhir ke posisi akar menimbulkan dua masalah sekaligus: nilai itu hilang, dan pohon tercecer. Urutan yang benar adalah menyimpan akar, memindahkan elemen terakhir ke akar, baru menjalankan sift down.
3. Memanggil pop pada heap kosong. Versi Python di atas melempar IndexError, dan perilaku ini justru membantu menemukan bug lebih awal. Periksa len(self.data) atau n == 0 dahulu bila kekosongan heap adalah kondisi yang wajar pada program.
4. Mengira push dan pop berbiaya konstan. Kedua operasi memang terasa seperti satu tukar, tetapi jumlah tukarnya paling banyak sepanjang tinggi pohon $\lfloor \log_2 n \rfloor$. Pada jutaan elemen, selisih $O(1)$ dengan $O(\log n)$ terasa nyata di akhir pengukuran.

Ringkasan#

• Push menempelkan nilai di ujung array lalu sift up memangkatnya selama induk lebih besar, dengan biaya $O(\log n)$.
• Pop menyimpan akar, memindahkan elemen terakhir ke akar, lalu sift down menurunkannya dengan selalu memilih anak terkecil.
• Heapify membangun heap dari array sembarang dalam $O(n)$ dengan sift down dari $\lfloor n/2 \rfloor - 1$ menuju akar.
• Logika yang sama berlaku di Java tanpa perubahan rumus, hanya berbeda pada pengelolaan kapasitas array.

Referensi#

• Algorithms, 4th Edition — Princeton University — materi priority queue Princeton yang menamai proses angkat dan turun pada heap sebagai swim dan sink.
• Heap (data structure) — Wikipedia — penjelasan operasi insert dan extract beserta biaya logaritmiknya pada binary heap.