Pengertian Struktur Data Heap
Struktur data heap adalah struktur data yang memiliki konsep seperti Binary Tree dengan aturan nilai data max heap dan min heap. Heap itu sendiri adalah array yang ada di bagian bawah, sedangkan yang ada di bagian atas hanyalah visualisasi dari heap.
Setiap elemen pada tree berkorespondensi dengan sebuah elemen pada array. Setiap level pada tree terisi penuh, kecuali yang terakhir, terisi dari kiri ke kanan.
Jenis Struktur Data Heap
1. Max-Heap
- Pada Max-Heap, nilai pada node akar (root) harus lebih besar dari nilai pada semua anaknya.
- Digunakan untuk mengimplementasikan antrian prioritas maksimum, di mana elemen dengan nilai tertinggi berada di atas.
2. Min-Heap
- Pada Min-Heap, nilai pada node akar (root) harus lebih kecil dari nilai pada semua anaknya.
- Digunakan untuk mengimplementasikan antrian prioritas minimum, di mana elemen dengan nilai terendah berada di atas
Operasi yang Terdapat pada Struktur Data Heap
1. Reorganisasi Heap
- Mengatur ulang elemen-elemen dalam heap untuk mempertahankan sifat heap.
2. Membentuk Heap
- Mengubah binary tree menjadi heap dengan mengatur ulang elemen-elemen.
3. Penyisipan Heap
- Menyisipkan elemen baru ke dalam heap, mempertahankan sifat heap.
4. Penghapusan Heap
- Menghapus elemen akar dari heap, kemudian mengatur ulang heap.
5. Pengurutan Heap (Heap Sort)
- Menggunakan heap untuk mengurutkan elemen-elemen dalam array.
Contoh Program Struktur Data Heap
import heapq
# Membuat heap kosong
heap = []
# Menambahkan elemen ke dalam heap
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
# Menghapus elemen terkecil dari heap
smallest = heapq.heappop(heap)
# Menampilkan elemen-elemen dalam heap
print("Elemen-elemen dalam heap:")
for elemen in heap:
print(elemen)
# Menampilkan elemen terkecil yang dihapus
print("Elemen terkecil yang dihapus:", smallest)
Penerapan Struktur Data Heap dalam Kehidupan Sehari-hari
Struktur data heap memiliki berbagai penerapan dalam kehidupan sehari-hari, di antaranya:
- Sistem Operasi: Heap digunakan dalam manajemen memori oleh sistem operasi untuk mengatur alokasi dan dealokasi memori.
- Grafik Komputer: Heap digunakan dalam algoritma pengurutan titik dalam grafik komputer.
- Pencarian Data: Heap digunakan dalam algoritma pencarian data seperti algoritma Dijkstra dan algoritma A*.
- Pengaturan Prioritas: Heap digunakan dalam implementasi antrian prioritas, di mana elemen dengan prioritas tertinggi diberikan akses terlebih dahulu.
- Manajemen Acara: Heap digunakan dalam manajemen acara untuk mengatur urutan acara berdasarkan prioritas.