Heap & Tries

HEAP

Ada 3 jenis :

a.       Min Heap

Root yang paling atas mempunyai nilai paling minimum.

Contoh :

b.      Max Heap

Root yang paling atas mempunyai nilai paling maximum.

Contoh :

c.       Min-Max Heap

Level paling atas minimum sedangkan level berikutnya maximum.

Contoh :

Representasi array :

(Current node = n)

parent = n / 2
left child = 2 * n
right child = (2 * n) + 1

PS : jika terjadi bilangan koma/decimal, bulatkan kebawah



INSERTION

1. Min-Heap

Insert new node (20)

pada gambar diatas, kita akan memasukan node 20 pada tree yang sudah ada. sesuai aturan binary Tree, 20 akan dimasukan di sebelah node 32.
Namun, posisi 20 setelah di insert adalah melanggar aturan, karena 20 lebih kecil dibandingkan parent nya yaitu 28. oleh karena itu terjadi penukaran tempat antara 20 dengan 28.

2. Max-Heap
insertion pada Max-Heap sama dengan Min-Heap, hanya berbeda aturan. aturan pada Max-Heap adalah Value Child < Value Parent-nya

3. Min-Max Heap
pada Min-Max Heap, min pada level 0(root) adalah yang bilangan min terkecil, dan max pada level 1 adalah bilangan max yang terbesar.

- jika yang di insert pada level min, maka parent nya (max) harus lebih besar daripada node yang akan di insert
- jika yang di insert pada level max, maka parent nya (min) harus lebih kecil dibandingkan node yang akan di insert

- setiap insert yang memenuhi kedua syarat diatas, harus mengecek value nya masing-masing terhadap min pada level 0/max pada level 1(tergantung yang di insert), jika terjadi pelanggaran syarat(yang sudah disebutkan diatas), maka harus dilakukan reposisi(downheap/upheap)

Tries

• Tries adalah tree yang dilakukan untuk menyimpan array asosiatif
• Properties pada tries:
• Setiap vertex/node merepresentasikan satu huruf
• Root merepresentasikan karakter kosong

Sekian. Terima kasih.