My first Magazine pemrograman-kompetitif-dasar | Page 129

10.2 Heap
2. Ulangi hingga seluruh data terurut menaik.
Pada selection sort, langkah pencarian elemen terkecil dilakukan dengan linear search.
Langkah ini bisa kita optimisasikan menggunakan struktur data heap , yang bisa mencari elemen
terkecil dengan kompleksitas logaritmik. Algoritma pengurutan menggunakan heap ini dinamakan
heapsort . Implementasinya ditunjukkan pada Algoritma 61.
Algoritma 61 Prosedur heapsort untuk mengurutkan array A dengan ukuran N secara menaik.
1:
2:
3:
4:
5:
6:
7:
procedure HEAPSORT (A, N)
MAKE H EAP (A, N)
for i ← 0, N − 1 do
A[i] ← TOP ()
POP ()
end for
end procedure
. Heap yang dibuat adalah min-heap
. Simpan elemen terkecil ke-i pada posisi ke-i
. Hapus elemen terkecil ke-i dari heap
Mari kita analisis kompleksitas dari algoritma heapsort . Sebagaimana dijelaskan pada bagian
sebelumnya, operasi MAKE H EAP memiliki kompleksitas waktu O(N). Kemudian, kita melakukan N
kali operasi POP , yang masing-masing memiliki kompleksitas waktu O(log N). Maka, kompleksitas
waktu dari algoritma heapsort adalah O(N + N log N) = O(N log N).
Heapsort memiliki kompleksitas waktu yang sama dengan quicksort maupun merge sort ,
yakni O(N log N). Namun, heapsort memiliki keuntungan yang tidak dimiliki keduanya, yaitu bisa
melakukan partial sort (pengurutan parsial).
Pengurutan parsial adalah aktivitas mengurutkan K elemen terkecil (atau terbesar) saja dari
suatu array . Selection sort juga bisa melakukan pengurutan parsial, namun membutuhkan waktu
O(NK). Dengan heapsort , untuk melakukan pengurutan parsial kita cukup melakukan operasi
POP sebanyak K kali saja. Kompleksitas waktunya menjadi O(N + K log N), yang lebih baik dari
O(NK).
119