Struktur data heap

 

Heap (struktur data)

Dalam ilmu komputer , heap adalah struktur data berbasis pohon yang memenuhi sifat heap : Dalam heap maksimum , untuk setiap simpul C yang diberikan, jika P adalah simpul induk dari C, maka kunci ( nilai ) dari P lebih besar dari atau sama dengan kunci dari C. Dalam heap minimum , kunci dari P lebih kecil dari atau sama dengan kunci dari C. ^[ 1 ] Simpul di "puncak" heap (tanpa induk) disebut simpul akar .

Contoh tumpukan biner maksimum dengan kunci simpul berupa bilangan bulat antara 1 dan 100

Heap adalah salah satu implementasi paling efisien dari tipe data abstrak yang disebut antrian prioritas , dan faktanya, antrian prioritas sering disebut sebagai "heap", terlepas dari bagaimana cara implementasinya. Dalam heap, elemen dengan prioritas tertinggi (atau terendah) selalu disimpan di root. Namun, heap bukanlah struktur yang diurutkan; heap dapat dianggap terurut sebagian. Heap adalah struktur data yang berguna ketika perlu menghapus objek dengan prioritas tertinggi (atau terendah) berulang kali, atau ketika penyisipan perlu diselingi dengan penghapusan simpul root.

Implementasi umum dari heap adalah binary heap , di mana pohonnya adalah pohon biner lengkap ^[ 2 ] (lihat gambar). Struktur data heap, khususnya binary heap, diperkenalkan oleh JWJ Williams pada tahun 1964, sebagai struktur data untuk algoritma penyortiran heapsort . ^[ 3 ] Heap juga penting dalam beberapa algoritma grafik yang efisien seperti algoritma Dijkstra . Ketika heap adalah pohon biner lengkap, ia memiliki tinggi sekecil mungkin—heap dengan N node dan cabang untuk setiap node selalu memiliki tinggi log _a N.

Perhatikan bahwa, seperti yang ditunjukkan dalam grafik, tidak ada urutan tersirat antara saudara kandung atau sepupu dan tidak ada urutan tersirat untuk penelusuran berurutan (seperti yang akan terjadi dalam, misalnya, pohon pencarian biner ). Hubungan tumpukan yang disebutkan di atas hanya berlaku antara node dan induknya, kakek-neneknya. Jumlah maksimum anak yang dapat dimiliki setiap node bergantung pada jenis tumpukan.

Tumpukan biasanya dibangun di tempat dalam larik yang sama tempat elemen disimpan, dengan strukturnya tersirat dalam pola akses operasi. Tumpukan berbeda dengan struktur data lain dengan batasan teoretis yang serupa atau dalam beberapa kasus lebih baik seperti pohon Radix karena tidak memerlukan memori tambahan selain yang digunakan untuk menyimpan kunci.