My first Magazine pemrograman-kompetitif-dasar | Page 128

10 Struktur Data NonLinear
for i ← bN/2c − 1 down to 0 do
HEAPIFY (i)
9:
end for
10: end procedure
. Lakukan proses heapify
7:
8:
5
3
4
2
1
Gambar 10.19: Ilustrasi urutan pelaksanaan heapify . Angka pada node menyatakan urutan
pelaksanaan heapify .
Analisis Pembangunan Heap Secara Efisien
Proses heapify melakukan N/2 kali operasi yang masing-masing memiliki kompleksitas
waktu O(log N), sehingga kompleksitas akhirnya terkesan O(N log N). Namun pada kasus ini,
sebenarnya setiap heapify tidak benar-benar O(log N). Kenyataannya, banyak operasi heapify
yang dilakukan pada tingkat bawah, yang relatif lebih cepat dari heapify pada tingkat di atas.
Perhitungan secara matematis 15 membuktikan bahwa kompleksitas keseluruhan MAKE H EAP
adalah O(N).
10.2.8
Catatan Implementasi Heap
Tentu saja, Anda dapat membuat heap dengan urutan yang terbalik, yaitu elemen terkecilnya
di atas. Dengan demikian, operasi yang didukung adalah mencari atau menghapus elemen
terkecil. Biasanya heap dengan sifat ini disebut dengan min-heap, sementara heap dengan
elemen terbesar di atas disebut dengan max-heap. Agar lebih rapi, Anda dapat menggunakan
struct (C) atau class (C++) pada implementasi heap . Bagi pengguna C++, struktur data
priority_queue dari header queue merupakan struktur data heap .
Pada ilmu komputer, heap dapat digunakan sebagai priority queue, yaitu antrean yang
terurut menurut suatu kriteria. Sifat heap juga dapat digunakan untuk optimisasi suatu algoritma.
Contoh paling nyatanya adalah untuk mempercepat algoritma Dijkstra, yang akan kita pelajari
pada Bab 11. Berbagai solusi persoalan greedy juga dapat diimplementasikan secara efisien
dengan heap . Heap dapat pula digunakan untuk pengurutan yang efisien, dan akan dibahas pada
bagian berikutnya.
Dengan mempelajari heap , Anda memperdalam pemahaman tentang bagaimana penggunaan
struktur data yang tepat dapat membantu menyelesaikan persoalan tertentu secara efisien.
10.2.9
Heapsort
Apakah Anda masih ingat dengan selection sort ? Berikut adalah ringkasan langkah-langkahnya:
1. Pilih elemen terkecil, lalu tempatkan di paling awal data.
118