Timbunan (struktur data)

Contoh timbunan maksimal (*max-heap*) dengan kunci simpul bernilai dari 1 hingga 100. Nilai pada simpul induk selalu lebih besar dari anak-anaknya.

Dalam ilmu komputer, timbunan atau tumpuk (bahasa Inggris: heapcode: en is deprecated ) adalah struktur data berbasis pohon khusus yang memenuhi sifat timbunan (heap property). Dalam literatur bahasa Indonesia, istilah "timbunan" lebih disarankan untuk digunakan guna menghindari kerancuan dengan struktur data stack (tumpukan).

Berdasarkan sifatnya, timbunan dibagi menjadi dua jenis utama:^[1]

Timbunan maksimal (Max-heap): Untuk setiap simpul C, jika P adalah simpul induk dari C, maka kunci (nilai) dari P selalu lebih besar dari atau sama dengan kunci C. Dengan demikian, nilai terbesar di seluruh struktur akan selalu berada di posisi paling atas atau akar (root).
Timbunan minimal (Min-heap): Untuk setiap simpul C, jika P adalah simpul induk dari C, maka kunci dari P selalu lebih kecil dari atau sama dengan kunci C. Nilai terkecil di seluruh struktur akan selalu berada di akar.

Timbunan merupakan salah satu implementasi struktur data yang paling efisien untuk membangun antrean prioritas (priority queue). Timbunan tidak sama dengan struktur data yang terurut secara ketat seperti pohon pencarian biner (BST). Timbunan hanya menjamin hubungan parsial antara induk dan anak, bukan urutan antarsaudara (kiri dan kanan).

Timbunan biner

Bentuk timbunan yang paling umum dijumpai adalah timbunan biner (binary heap). Timbunan biner adalah sebuah pohon biner lengkap (complete binary tree), di mana seluruh tingkat pohon terisi penuh kecuali mungkin pada tingkat paling bawah, dan simpul-simpul pada tingkat terbawah diisi dari sisi paling kiri.^[2]

Karena strukturnya yang padat dan teratur, timbunan biner hampir selalu diimplementasikan secara efisien menggunakan larik (array) biasa, tanpa memerlukan penunjuk (pointer) sama sekali.

Jika elemen akar diletakkan pada indeks 0 dalam larik, maka untuk setiap simpul pada indeks $i$ , posisi kerabatnya dapat dihitung dengan operasi aritmetika dasar:

Indeks simpul induk: $\lfloor (i-1)/2\rfloor$
Indeks simpul anak kiri: $2i+1$
Indeks simpul anak kanan: $2i+2$

Pendekatan menggunakan larik ini membuat timbunan sangat cepat secara komputasi karena memanfaatkan lokalitas rujukan (cache locality) yang ramah terhadap memori prosesor.

Operasi dasar

Operasi-operasi pada timbunan biasanya memiliki kompleksitas waktu yang sangat terukur secara logaritmik:^[1]

Mencari elemen puncak (Peek / Find-Max / Find-Min): Mengembalikan nilai dari elemen akar tanpa menghapusnya. Operasi ini berjalan dalam waktu konstan $O(1)$ .
Menyisipkan elemen (Insert / Push): Elemen baru ditambahkan pada akhir tumpukan (posisi terbawah pohon), lalu "diapungkan" ke atas (bubble up atau sift-up) dengan cara ditukar berulang kali dengan simpul induknya hingga sifat timbunan terpenuhi. Kompleksitas waktunya adalah $O(\log n)$ .
Mengekstrak elemen puncak (Extract-Max / Extract-Min / Pop): Mengambil dan menghapus elemen akar. Posisi akar kemudian digantikan oleh elemen paling terakhir di dasar pohon. Elemen tersebut lalu "ditenggelamkan" (sift-down atau heapify) ke bawah dengan cara ditukar dengan salah satu anaknya yang lebih besar (atau lebih kecil) hingga sifat timbunan kembali terpenuhi. Kompleksitas waktunya adalah $O(\log n)$ .

Pemanfaatan

Timbunan memiliki peran penting dalam berbagai algoritme dan rekayasa perangkat lunak:

Antrean Prioritas: Sistem penjadwalan pada sistem operasi dan rekayasa lalu lintas jaringan menggunakan antrean prioritas berbasis timbunan untuk menentukan tugas mana yang harus diproses terlebih dahulu berdasarkan nilai bobotnya.
Pengurutan Timbunan (Heapsort): Heapsort adalah salah satu algoritme pengurutan perbandingan yang sangat stabil dan dilakukan di tempat (in-place). Algoritme ini pertama-tama mengubah larik menjadi struktur timbunan, lalu secara berulang mengekstrak nilai puncaknya untuk mendapatkan hasil yang terurut dalam waktu komputasi maksimal $O(n\log n)$ .^[3]
Algoritme Graf: Timbunan minimal secara ekstensif digunakan untuk mengefisienkan algoritme graf populer, seperti Algoritme Dijkstra (untuk mencari rute terpendek) dan algoritme Prim (untuk mencari pohon rentang minimum).

Lihat pula

Referensi

^ ^a ^b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (dalam bahasa Inggris) (Edisi 3rd). MIT Press. ISBN 978-0-262-03384-8.
^ Black, Paul E. "heap". Dictionary of Algorithms and Data Structures (dalam bahasa Inggris). National Institute of Standards and Technology. Diakses tanggal 2 Juni 2026.
^ Black, Paul E. "heapsort". Dictionary of Algorithms and Data Structures (dalam bahasa Inggris). National Institute of Standards and Technology. Diakses tanggal 2 Juni 2026.