HEAP &
TRIES
1.
Heap
Dalam ilmu komputer, sebuah heap adalah struktur data yang berdasarkan konsep struktur
data pohon. Di heap, juga diterapkan konsep binary tree.
Terdapat
3 jenis heap, diantaranya :
a. Min heap
Min
heap merupakan heap yang node rootnya adalah angka terkecil dan setiap anak dari
rootnya selalu lebih kecil daripada parentnya. Biasanya min heap ini, dia ascending
( dari terkecil ke terbesar ).
b. Max heap
Max
heap ini sama seperti min heap, tapi bedanya adalah angka yang berada di root
adalah angka terbesar dan max heap ini descending ( dari terbesar ke terkecil ).
c. Min Max heap
Untuk
min max heap ini cukup unik, dimana root dari heap ini merupakan angka terkecil
didalam tree nya, tapi angka yang berada dii node anak dari sebuah root
merupakan angka paling besar dan berlaku seterusnya sampai ke bawah.
Berikut adalah contoh
dari semua heap yang telah dijelaskan.
Untuk menentukan dimana letak parent, left child, dan right
child dari heap kita, kita memiliki formula sebagai berikut :
a.
Parent : MyIdx/2;
b.
Left Child : MyIdx*2;
c.
Right Child : (MyIdx*2)+1;
Sama
seperti tree lainnya, kita juga dapat
melakukan insertion dan deletion dalam heap ini. Penjelasannya sebagai
berikut :
a.
Min heap & Max heap insertion
Langkah untuk melakukan
insertion pada min heap :
1.
Buat node baru di heap
paling akhir/ bawah
2.
Masukan nilai di node
yang baru dibentuk itu
3.
Bandingkan nilai yang di
node baru dengan parentnya
4.
Jika angka pada node baru
lebih kecil daripada angka di node parent, maka tukar mereka. Jika angka di
node baru lebih besar, diamkan saja
5. Ulangi langkah 3 dan 4 sampai heap terurut.
Langkah untuk melakukan
insertion pada max heap :
1.
Buat node baru di heap
paling akhir/ bawah
2.
Masukan nilai di node
yang baru dibentuk itu
3.
Bandingkan nilai yang di
node baru dengan parentnya
4.
Jika angka pada node baru
lebih besar daripada angka di node parent, maka tukar mereka. Jika angka di
node baru lebih kecil, diamkan saja
5.
Ulangi langkah 3 dan 4
sampai heap terurut.
b.
Min heap & Max heap deletion
Langkah untuk melakukan deletion pada min heap :
1.
Hilangkan angka pada
node root
2.
Pindahkah elemen
terakhir ke bagian root
3.
Bandingkan nilai dari
node child dengan parentsnya
4.
Jika nilai dari
parentnya lebih besar daripada node childnya, maka tukar nilainya
5. Ulangi langkah 3 dan 4 sampai heap terurut.
Langkah untuk melakukan
deletion pada max heap :
1.
Hilangkan angka pada
node root
2.
Pindahkah elemen
terakhir ke bagian root
3.
Bandingkan nilai dari
node child dengan parentsnya
4.
Jika nilai dari
parentnya lebih kecil daripada node childnya, maka tukar nilainya
5.
Ulangi langkah 3 dan 4
sampai heap terurut.
c.
Min Max heap insertion
Langkah untuk melakukan insertion pada min max heap :
1.
Tambahkan node baru di
akhir heap. Ini mungkin dapat menghancurkan min max heap tree, tapi kita dapat
melalukan pengurutan padanya.
2.
Masukan angka pada node
baru tersebut.
3.
Lakukan upheap untuk pada
elemen yang ada. Namun, upheap pada min max heap sedikit berbeda dengan yang
lain.
4. Jika node baru ada di bagian min :
Jika node
parent dari node baru ini lebih kecil daripada node baru, maka swap mereka dan
upheapmax dari parentnya, kalau tidak upheapmin node barunya.
5. Jika node baru ada di bagian max :
Jika
node parent dari node baru ini angkanya lebih besar daripada anaknya, maka swap
nilai mereka dan upheapmin dari parentsnya. Kalau tidak, upheapmax node
barunya.
d.
Min Max heap deletion
Terdapat
2 jenis deletion disini, tergantung pada keinginan user dimana terdapat
deletion pada minimum dan deletion pada maximum. Jika deletion pada minimum,
lakukan deletion seperti yang ada di min heap. Sedangkan deletion pada max
heap, lakukan deletion seperti max heap, tapi disini bandingkan nilai node baru
yang ada dengan node max dan pilih diantara node ke 2 atau ke 3 sebagai node
max.
2.
Tries
Tries disini sama dengan
kebanyakan tree pada umumnya, tapi pada tree yang kita temukan hingga sekarang,
mereka mengisinya dengan angka disetiap nodenya. Tapi di tries, kita akan
menggunakan dengan next levelnya lagi, yaitu diisi dengan character huruf.
Implementasi trie ini bisa anda temukan di game yang seperti susun kalimat,
dapat juga ditemukan pada google search dimana kita mengetik 1 huruf, akan
keluar recommended yang diberikan oleh google. Misalkan kita mengetik Y, maka
dapat ditemukan banyak rekomendasi yang diberikan oleh google.
Seperti itu contoh pencarian di google.
Di trie ini, mereka selalu memiliki
1 parent yang sama dan beberapa jenis cabang di bawahnya. Nah di cabang ini
dapat bercabang lagi dan seterusnya. Dan bisa menghasilkan kata yang masuk akal
disana.
Sekian penjelasan saya tentang Heap
dan Tries ini. Semoga bermanfaat 😊
Komentar
Posting Komentar