STRUKTUR DATA HEAP
STRUKTUR DATA HEAP
Struktur data heap adalah struktur data yang berbentuk pohon biner yang memiliki sifat tertentu, seperti heap maksimum atau minimum. Struktur data ini memiliki beberapa kegunaan, di antaranya:
- Pengurutan data
- Mendapatkan elemen maksimum atau minimum dengan cepat
- Menghapus objek dengan prioritas tertinggi (atau terendah) secara berulang
- Menyisipkan data yang diselingi dengan penghapusan simpul akar
Heap memiliki beberapa karakteristik, yaitu:
- Dalam Min Heap, nilai setiap simpul induk lebih kecil atau sama dengan nilai anak-anaknya
- Dalam Max Heap, nilai setiap simpul induk lebih besar atau sama dengan nilai anak-anaknya
Heap biasanya diimplementasikan dengan array. Karena heap biner selalu merupakan pohon biner lengkap, heap dapat disimpan secara ringkas.
Heap merupakan cara umum untuk mengimplementasikan antrian prioritas. Antrian prioritas memiliki banyak aplikasi, salah satunya adalah dalam algoritma grafik seperti dalam algoritma Dijkstra untuk menemukan jarak terpendek antara dua simpul.
Komentar
Posting Komentar