Timbunan (struktur data) - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T04:05:34Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 04.05
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).		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 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.		* '''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 ==		== 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.		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 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>.		* '''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.		* '''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]]).		* '''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)]]		* [[Antrean (struktur data)]]
	* [[Larik]]		* [[Larik]]

	~~== Referensi ==~~


	== Pranala luar ==		== Pranala luar ==


	* [http://mathworld.wolfram.com/Heap.html Heap] di situs Wolfram MathWorld		* [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://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		* [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: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29306774; atribusi sumber disertakan.

2026-08-23T03:26:11Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29306774; atribusi sumber disertakan.

Halaman baru

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:
* '''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.

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

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.

Jika elemen akar diletakkan pada indeks <code>0</code> dalam larik, maka untuk setiap simpul pada indeks <math>i</math>, posisi kerabatnya dapat dihitung dengan operasi aritmetika dasar:
* Indeks simpul induk: <math>\lfloor(i - 1) / 2\rfloor</math>
* Indeks simpul anak kiri: <math>2i + 1</math>
* Indeks simpul anak kanan: <math>2i + 2</math>

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 [[Notasi Big O|kompleksitas waktu]] yang sangat terukur secara logaritmik:

* '''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>.
* '''Menyisipkan elemen''' (<code>Insert</code> / <code>Push</code>): 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 <math>O(\log n)</math>.
* '''Mengekstrak elemen puncak''' (<code>Extract-Max</code> / <code>Extract-Min</code> / <code>Pop</code>): 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 <math>O(\log n)</math>.

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

* '''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>.
* '''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 ==
* [[Struktur data]]
* [[Pohon (struktur data)]]
* [[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

== 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). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.