Timbunan (struktur data): Perbedaan antara revisi

Revisi terkini sejak 23 Agustus 2026 04.05

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 () 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: $⌊ (i - 1) / 2 ⌋$
Indeks simpul anak kiri: $2 i + 1$
Indeks simpul anak kanan: $2 i + 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:^[3]

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)$ .^[4]
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

Pranala luar

Heap di situs Wolfram MathWorld
heap dalam Dictionary of Algorithms and Data Structures NIST
Penjelasan cara kerja algoritma heap

Referensi

↑ Thomas H. Cormen. Introduction to Algorithms. MIT Press. 2009. ISBN 978-0-262-03384-8.
↑ Paul E. Black. heap. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology.
↑ Thomas H. Cormen. Introduction to Algorithms. MIT Press. 2009. ISBN 978-0-262-03384-8.
↑ Paul E. Black. heapsort. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology.

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 29306774 (2026-06-02T11:45:49Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

[1] Thomas H. Cormen. Introduction to Algorithms. MIT Press. 2009. ISBN 978-0-262-03384-8.

[2] Paul E. Black. heap. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology.

[3] Thomas H. Cormen. Introduction to Algorithms. MIT Press. 2009. ISBN 978-0-262-03384-8.

[4] Paul E. Black. heapsort. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology.

[1]

[2]

[3]

[4]

@@ Baris 1: / Baris 1: @@
+[[File:Max-Heap.svg|thumb|right|280px|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''' () adalah [[struktur data]] berbasis [[Pohon (struktur data)|pohon]] khusus yang memenuhi '''sifat timbunan''' (''heap property''). Dalam literatur bahasa Indonesia, istilah "timbunan" lebih disarankan untuk digunakan guna menghindari kerancuan dengan struktur data ''[[Tumpukan (struktur data)|stack]]'' (tumpukan).
-Berdasarkan sifatnya, timbunan dibagi menjadi dua jenis utama:
+Berdasarkan sifatnya, timbunan dibagi menjadi dua jenis utama:<ref>Thomas H. Cormen. ''Introduction to Algorithms''. MIT Press. 2009. ISBN 978-0-262-03384-8.</ref>
 * '''Timbunan maksimal''' (''Max-heap''): Untuk setiap [[Simpul (ilmu komputer)|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 [[Pohon (struktur data)|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.
@@ Baris 8: / Baris 10: @@
 == Timbunan biner ==
-Bentuk timbunan yang paling umum dijumpai adalah '''timbunan biner''' (''binary heap''). Timbunan biner adalah sebuah [[Pohon biner|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.
+Bentuk timbunan yang paling umum dijumpai adalah '''timbunan biner''' (''binary heap''). Timbunan biner adalah sebuah [[Pohon biner|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.<ref>Paul E. Black. [https://xlinux.nist.gov/dads/HTML/heap.html heap]. ''Dictionary of Algorithms and Data Structures''. National Institute of Standards and Technology.</ref>
 Karena strukturnya yang padat dan teratur, timbunan biner hampir selalu diimplementasikan secara efisien menggunakan [[Larik|larik]] (''array'') biasa, tanpa memerlukan [[Penunjuk (ilmu komputer)|penunjuk]] (''pointer'') sama sekali.
@@ Baris 20: / Baris 22: @@
 == Operasi dasar ==
-Operasi-operasi pada timbunan biasanya memiliki [[Notasi Big O|kompleksitas waktu]] yang sangat terukur secara logaritmik:
+Operasi-operasi pada timbunan biasanya memiliki [[Notasi Big O|kompleksitas waktu]] yang sangat terukur secara logaritmik:<ref>Thomas H. Cormen. ''Introduction to Algorithms''. MIT Press. 2009. ISBN 978-0-262-03384-8.</ref>
 * '''Mencari elemen puncak''' (<code>Peek</code> / <code>Find-Max</code> / <code>Find-Min</code>): Mengembalikan nilai dari elemen akar tanpa menghapusnya. Operasi ini berjalan dalam waktu konstan <math>O(1)</math>.
@@ Baris 30: / Baris 32: @@
 * '''Antrean Prioritas''': Sistem penjadwalan pada [[Sistem operasi|sistem operasi]] dan rekayasa [[Lalu lintas jaringan|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 [[Algoritma pengurutan|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 <math>O(n \log n)</math>.
+* '''Pengurutan Timbunan (''Heapsort'')''': ''[[Heapsort]]'' adalah salah satu [[Algoritma pengurutan|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 <math>O(n \log n)</math>.<ref>Paul E. Black. [https://xlinux.nist.gov/dads/HTML/heapsort.html heapsort]. ''Dictionary of Algorithms and Data Structures''. National Institute of Standards and Technology.</ref>
 * '''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]]).
@@ Baris 38: / Baris 40: @@
 * [[Antrean (struktur data)]]
 * [[Larik]]
-== Referensi ==
 == Pranala luar ==
 *  [http://mathworld.wolfram.com/Heap.html Heap]  di situs Wolfram MathWorld
 *  [https://xlinux.nist.gov/dads/HTML/heap.html ''heap'' dalam ''Dictionary of Algorithms and Data Structures'' NIST]
 *  [https://www.cs.auckland.ac.nz/software/AlgAnim/heaps.html Penjelasan]  cara kerja algoritma heap
+== Referensi ==
+<references />
+== Sumber dan atribusi ==
-== Sumber dan atribusi ==
+Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Timbunan+%28struktur+data%29&oldid=29306774 Wikipedia bahasa Indonesia], revisi 29306774 (2026-06-02T11:45:49Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.
-Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Timbunan+%28struktur+data%29&oldid=29306774 Wikipedia bahasa Indonesia], revisi 29306774 (2026-06-02T11:45:49Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.
+<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script (bicara | kontrib)