My first Magazine pemrograman-kompetitif-dasar | Page 121

10.2 Heap
9
7
8
7
5
3
1
4
6
2
4
Gambar 10.10: Tahap 4: Penukaran lanjutan nilai pada node baru dengan parent -nya karena
nilainya juga lebih kecil.
9
7
8
7
5
1
3
4
6
2
4
Gambar 10.11: Tahap 5: Node baru telah memenuhi kondisi yang diperlukan pada heap , operasi
push selesai
Kasus terburuk terjadi ketika pertukaran yang terjadi paling banyak. Hal ini terjadi ketika
elemen yang dimasukkan merupakan nilai yang paling besar pada heap . Banyaknya pertukaran
yang terjadi sebanding dengan kedalaman dari complete binary tree, yaitu O(log N). Dengan
demikian, kompleksitas untuk operasi push adalah O(log N).
10.2.4
Operasi Pop
Operasi pop pada binary heap dilakukan dengan 3 tahap:
1. Tukar posisi elemen pada root dengan elemen terakhir mengikuti aturan complete binary
tree.
2. Buang elemen terakhir binary heap , yang telah berisi elemen dari root.
3. Selama elemen yang ditukar ke posisi root memiliki anak langsung yang berelemen lebih
besar, tukar elemen tersebut dengan salah anaknya yang memiliki elemen terbesar.
Misalkan akan dilakukan pop pada heap pada Gambar 10.11. Untuk selanjutnya, Gambar
10.12 sampai dengan Gambar 10.16 akan menggambarkan simulasi secara bertahap untuk
operasi pop .
111