Timbunan (struktur data) 📖 Wikipedia

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).

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 ${\displaystyle i}$, posisi kerabatnya dapat dihitung dengan operasi aritmetika dasar:

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

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

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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle O(\log n)}$.

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 ${\displaystyle 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).

• Struktur data
• Pohon (struktur data)
• Antrean (struktur data)
• Larik

Wikimedia Commons memiliki media mengenai Heap data structures.

Wikibooks Data Structures memiliki halaman di:

Min and Max Heaps

• (Inggris) Heap Diarsipkan 2020-05-15 di Wayback Machine. di situs Wolfram MathWorld
• (Inggris) heap dalam Dictionary of Algorithms and Data Structures NIST
• (Inggris) Penjelasan Diarsipkan 2022-03-16 di Wayback Machine. cara kerja algoritma heap