My first Magazine pemrograman-kompetitif-dasar | Page 125

10.2 Heap
Algoritma 54 Fungsi-fungsi pembantu yang memudahkan implementasi heap .
function GET P ARENT (x)
2:
return (x − 1) div 2
3: end function
1:
function GET L EFT (x)
return 2x + 1
6: end function
4:
5:
function GET R IGHT (x)
8:
return 2x + 2
9: end function
7:
Algoritma 55 Prosedur untuk melakukan push pada heap .
1:
2:
3:
4:
5:
6:
7:
8:
9:
procedure PUSH (val)
i ← size
arrHeap[i] ← val
while (i > 0) ∧ (arrHeap[i] > arrHeap[ GET P ARENT (i)]) do
SWAP (arrHeap[i], arrHeap[ GET P ARENT (i)])
i ← GET P ARENT (i)
end while
size ← size + 1
end procedure
Algoritma 56 Prosedur untuk melakukan pop pada heap .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
procedure POP ()
SWAP (arrHeap[0], arrHeap[size − 1])
size ← size − 1
. Lakukan pembuangan pada elemen terakhir
i ← 0
swapped ← true
while swapped do
. Perulangan untuk perbaikan struktur heap
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
115