My first Magazine pemrograman-kompetitif-dasar | Page 123

10.2 Heap
8
7
7
4
5
1
3
6
2
4
Gambar 10.16: Tahap 5: Kini sudah tidak ada anak yang bernilai lebih besar, operasi pop selesai.
Kasus terburuk juga terjadi ketika pertukaran yang terjadi paling banyak. Hal ini terjadi
ketika elemen yang ditempatkan di root cukup kecil, sehingga perlu ditukar sampai ke tingkat
paling bawah. Banyaknya pertukaran yang terjadi sebanding dengan kedalaman dari complete
binary tree. Dengan demikian, kompleksitas untuk operasi pop adalah O(log N).
10.2.5
Operasi Top
Operasi top adalah operasi untuk mengambil nilai terbesar pada heap . Karena setiap node
memiliki nilai yang lebih besar daripada node anak-anaknya, maka nilai terbesar dari seluruh
heap selalu terletak di root. Oleh karena itu, operasi ini cukup mengembalikan nilai dari root.
Kompleksitas operasi ini adalah O(1).
Dengan demikian, berkat penerapan heap , seluruh operasi pada persoalan Hobi Batu Akik
dapat dilakukan dengan efisien. Tabel 10.2 menunjukkan kompleksitas masing-masing operasi
untuk solusi dengan insertion sort dan dengan heap .
Tabel 10.2: Perbandingan kompleksitas solusi Hobi Batu Akik.
Operasi
Dengan insertion sort Dengan heap
simpan(x)
O(N)
O(log N)
lihat()
O(1)
O(1)
jual()
O(1)
O(log N)
10.2.6
Implementasi Binary Heap
Untuk mengimplementasikan binary heap , dibutuhkan implementasi dari tree . Implementasi
representasi tree dapat menggunakan teknik representasi graf yang telah dipelajari sebelumnya.
Namun, untuk tree dengan kondisi tertentu, kita dapat menggunakan representasi yang lebih
sederhana. Terutama pada kasus ini, yang mana tree yang diperlukan adalah complete binary
tree.
Complete binary tree dapat direpresentasikan dengan sebuah array . Misalkan array ini
bersifat zero-based, yaitu dimulai dari indeks 0. Elemen pada indeks ke-i menyatakan elemen
pada node ke-i. Anak kiri dari node ke-i adalah node ke-(2i + 1). Anak kanan dari node ke-i
adalah node ke-(2i + 2).
113