My first Magazine pemrograman-kompetitif-dasar | Page 117

10.2 Heap
Algoritma 51 Pencarian perwakilan kelompok dari suatu elemen x yang efisien dengan path
compression.
1:
2:
3:
4:
5:
6:
7:
8:
function FIND R EPRESENTATIVE (x)
if par[x] = x then
return x
else
par[x] ← FIND R EPRESENTATIVE (par[x])
return par[x]
end if
end function
. Catat elemen representatifnya
Operasi check
Operasi untuk memeriksa apakah a dan b berada pada kelompok yang sama dapat dilakukan
dengan memeriksa apakah keduanya memiliki perwakilan kelompok yang sama. Hal ini ditunjukkan
pada Algoritma 52.
Algoritma 52 Implementasi pemeriksaan apakah a dan b berada pada kelompok yang sama.
function CHECK (a, b)
return FIND R EPRESENTATIVE (a) = FIND R EPRESENTATIVE (b)
3: end function
1:
2:
10.1.2
Analisis Kompleksitas
Apabila seluruh parent elemen sudah dikenakan path compression, maka setiap elemen
langsung menunjuk ke elemen perwakilan kelompoknya. Artinya, kini fungsi FIND R EPRESENTATIVE
bekerja dalam O(1). Kompleksitas satu kali pemanggilan FIND R EPRESENTATIVE tidak dapat
didefinisikan secara pasti. Perhitungan secara matematis membuktikan bahwa dengan path
compression, kompleksitas untuk M operasi FIND R EPRESENTATIVE dan N − 1 operasi JOIN ,
dengan M ≥ N, bekerja dalam O(M log N). 14
10.2
Heap
Heap merupakan struktur data yang umum dikenal pada ilmu komputer. Nama heap sendiri
berasal dari Bahasa Inggris, yang berarti "gundukan". Heap merupakan struktur data yang
mampu mencari nilai terbesar secara efisien dari sekumpulan elemen yang terus bertambah.
Untuk lebih jelasnya, perhatikan contoh berikut.
Contoh Soal 10.2: Hobi Batu Akik
Di belakang peternakan Pak Dengklek, terdapat sebuah gua yang kaya akan batu akik.
Setiap kali Pak Dengklek melewatinya, ia akan mengambil sebuah batu akik untuk dibawa
pulang. Karena pernah belajar ilmu kebumian, Pak Dengklek dapat menilai seberapa
berharganya batu akik yang ia ambil. Untuk kemudahan, Pak Dengklek memberikan nilai
harga tersebut berupa suatu bilangan bulat.
107