My first Magazine pemrograman-kompetitif-dasar | Page 127

10.2 Heap
Algoritma 58 Prosedur untuk melakukan heapify pada heap .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
procedure HEAPIFY (rootIdx)
i ← rootIdx
swapped ← true
while swapped do
maxIdx ← i
if ( GET L EFT (i) < size) ∧ (arrHeap[maxIdx] < arrHeap[ GET L EFT (i)]) then
maxIdx ← GET L EFT (i)
end if
if ( GET R IGHT (i) < size) ∧ (arrHeap[maxIdx] < arrHeap[ GET R IGHT (i)]) then
maxIdx ← GET R IGHT (i)
end if
SWAP (arrHeap[i], arrHeap[maxIdx])
swapped ← (maxIdx 6 = i)
. true bila terjadi pertukaran
i ← maxIdx
end while
end procedure
Dengan adanya operasi heapify , operasi pop sendiri dapat kita sederhanakan seperti yang
ditunjukkan pada Algoritma 59.
Algoritma 59 Operasi pop yang disederhanakan dengan heapify .
procedure POP ()
SWAP (arrHeap[0], arrHeap[size − 1])
3:
size ← size − 1
4:
HEAPIFY (0)
5: end procedure
1:
2:
. Lakukan pembuangan pada elemen terakhir
Sekali melakukan heapify , kasus terburuknya adalah elemen root dipindahkan hingga ke
paling bawah tree . Jadi kompleksitasnya adalah O(H), dengan H adalah ketinggian dari com-
plete binary tree. Berhubung H = O(log N), dengan N adalah banyaknya elemen pada heap ,
kompleksitas heapify adalah O(log N).
Implementasi Pembangunan Heap Secara Efisien
Setelah memahami heapify , kita dapat menulis prosedur pembangunan heap dari array A
berisi N elemen secara efisien. Prosedur ini ditunjukkan pada Algoritma 60. Elemen terakhir
yang berada pada tingkat kedua paling bawah dapat ditemukan dengan mudah, yaitu elemen
dengan indeks N/2 dibulatkan ke bawah dan dikurangi 1.
Algoritma 60 Prosedur untuk membuat heap secara efisien dari array A.
1:
2:
3:
4:
5:
6:
procedure MAKE H EAP (A, N)
INITIALIZE H EAP (N)
for i ← 0, N − 1 do
arrHeap[size] ← A[i]
size ← size + 1
end for
. Salin array A ke array heap
117