My first Magazine pemrograman-kompetitif-dasar | Page 126

10 Struktur Data NonLinear
Algoritma 57 Fungsi untuk melakukan top pada heap
function TOP ()
2:
return arrHeap[0]
3: end function
1:
10.2.7
Pembangunan Heap Secara Efisien
Ketika Anda memiliki data N elemen, dan hendak dimasukkan ke dalam heap , Anda dapat:
1. Membuat heap kosong, lalu melakukan push satu per satu hingga seluruh data dimuat
heap . Kompleksitasnya O(N log N), atau
2. Membuat array dengan N elemen, lalu array ini dibuat menjadi heap dalam O(N) menggu-
nakan cara yang lebih efisien.
Untuk membuat heap dari N elemen secara efisien, kita dapat membuat array dengan N
elemen, lalu isi array ini dengan elemen-elemen yang akan dimasukkan pada heap . Kemudian
lakukan langkah berikut untuk masing-masing node , mulai dari tingkat kedua dari paling bawah
sampai ke tingkat paling atas:
1. Misalkan node ini adalah node x.
2. Jadikan subtree yang bermula pada node x ini agar membentuk heap dengan suatu operasi
baru, yaitu heapify .
Heapify adalah operasi untuk membentuk sebuah heap yang bermula pada suatu node ,
dengan asumsi anak kiri dan anak kanan node tersebut sudah membentuk heap .
x
heap
heap
Gambar 10.18: Operasi heapify hanya dapat bekerja apabila subtree kiri dan subtree kanan
dari root telah membentuk heap .
Berhubung kedua anak telah membentuk heap , kita cukup memindahkan elemen root ke
posisi yang tepat. Jika elemen root sudah lebih besar daripada elemen anaknya, tidak ada yang
perlu dilakukan. Sementara bila elemen root lebih kecil daripada salah satu elemen anaknya,
tukar elemennya dengan elemen salah satu anaknya yang paling besar. Kegiatan ini sebenarnya
sangat mirip dengan yang kita lakukan pada operasi pop . Heapify dapat diimplementasikan
seperti yang ditunjukkan pada Algoritma 58.
116