My first Magazine pemrograman-kompetitif-dasar | Page 119

10.2 Heap
10.2.1
Konsep Heap
Secara umum, heap mendukung operasi-operasi sebagai berikut:
• push , yaitu memasukkan elemen baru ke penyimpanan.
• pop , yaitu membuang elemen terbesar dari penyimpanan.
• top , yaitu mengakses elemen terbesar dari penyimpanan.
Operasi heap tersebut dapat diimplementasikan dengan berbagai cara. Kita akan mempela-
jari salah satunya, yaitu binary heap .
10.2.2
Struktur Binary Heap
Struktur data Binary Heap memiliki sifat:
• Berstruktur complete binary tree.
• Setiap node merepresentasikan elemen yang disimpan pada heap .
• Setiap node memiliki nilai yang lebih besar daripada node anak-anaknya.
9
7
7
4
5
3
1
6
2
4
Gambar 10.5: Contoh binary heap .
9
7
7
9
5
1
3
7
2
4
Gambar 10.6: Contoh bukan binary heap .
Pada gambar 10.6, pohon tersebut bukanlah sebuah binary heap . Perhatikan node yang
ditandai. Node tersebut memiliki nilai 7, sementara salah satu anaknya memiliki nilai 9. Ini
melanggar aturan setiap node memiliki nilai yang lebih besar daripada node anak-anaknya.
Binary heap perlu memiliki struktur seperti ini untuk menjamin operasi-operasinya dapat
dilakukan secara efisien. Misalkan N adalah banyaknya elemen yang sedang disimpan. Operasi
push dan pop bekerja dalam O(log N), sementara top bekerja dalam O(1). Kita akan melihat
satu per satu bagaimana operasi tersebut dilaksanakan.
109