HEAP & TRIES

HEAP
- Min heap: nilai child selalu lebih besar, makin ke bawah makin besar nilainya.
- Max heap: nilai child selalu lebih kecil, root paling besar nilainya.
- Min max heap: min - max - min - max. Root selalu paling minimum, anak dari root selalu maksimum

Heap biasanya menggunakan array. Array dimulai dengan index 0, sedangkan heap dimulai dari 1.
Rumus mencari parent = index sekarang/2
Rumus mencari left child = index sekarang*2
Rumus mencari right child = (index sekarang*2)+1

Insertion Min Heap

Taruh di array index terakhir (buat baru) lalu up head bandingin dengan parentnya apakah dirinya lebih kecil dari parent, kalau lebih kecil tukar posisi dengan parent. Dilakukan berulang hingga syarat lebih kecil tersebut tidak memenuhi.

Insertion Max Heap 

Taruh di array index terakhir (buat baru) lalu up head bandingin dengan parentnya apakah dirinya lebih besar dari parent, kalau lebih besar tukar posisi dengan parent. Dilakukan berulang hingga syarat lebih besar tersebut tidak memenuhi.

Deletion Min Heap

Selalu delete root, kemudian digantikan dengan array dari index terakhir (terujung akhir), lalu bandingkan dengan childnya. Jika childnya lebih kecil dari dirinya maka tukar posisi, ulangi sampai syarat tersebut tidak berlaku.

Deletion Max Heap
Selalu delete root, kemudian digantikan dengan array dari index terakhir (terujung akhir), lalu bandingkan dengan childnya. Jika childnya lebih besar dari dirinya maka tukar posisi, jika keduanya lebih besar maka pilih nilai yang paling besar, ulangi sampai syarat tersebut tidak berlaku.

Heap Sort
Min sort = ascending
Max sort = descending

Cara min sort: tampung root di suatu variabel, lalu index terakhir dari array menggantikannya. Bandingkan dengan anak - anaknya (down heap) cari yang terkecil, lalu tukar posisi dengan anak yang lebih kecil. Lalu old root yang sudah dipindahkan ke child bandingkan lagi dengan childnya yang baru, apabila child lebih kecil maka tukar posisi. Lakukan berulang hingga syarat tidak terpenuhi.

Cara max sort: tampung root di suatu variabel, lalu index terakhir dari array menggantikannya. Bandingkan dengan anak - anaknya (down heap) cari yang terbesar lalu tukar posisi dengan anaknya yang terbesar lebih besar dari dirinya. Lalu old root yang sudah pindah ke bawah bandingkan lagi dengan childnya yang baru, bandingkan dengan childnya bila childnya lebih besar maka tukar posisi dengan dirinya. Ulangi sampai syarat tidak terpenuhi

Min - Max Heap

Nilai paling minimal selalu array[1], dan yang paling maksimal selalu array[2] atau array[3]. Jika pada level min, maka nilainya lebih kecil dari parentnya, jika pada level max maka nilainya selalu lebih besar daripada parentnya.

Insert Min - Max Heap
Taruh dahulu pada array terakhir (terujung baru), lalu jika ia pada level max maka bandingkan dengan grandparentnya yang tentunya level max juga, jika dirinya lebih besar maka tukar posisi dengan grandparent. Lalu old grandparent tadi yang ditukar, bandingkan dengan parentnya yaitu si level min, jika dirinya lebih kecil dari parent maka tukar posisi.

Deletion Min - Max Heap
Delete bisa terjadi dari nilai min atau maxnya. Contoh dari nilai min, gantikan dengan array terakhir (terujung) lalu bandingkan dengan grandchildnya yang terletak pada level min juga, apabila grandchild lebih kecil dari dirinya maka tukar posisi. Ulangi lagi bandingkan lagi hingga syarat tidak terpenuhi.

TRIES

Menyicil karakter untuk menyusun kata - kata. Contoh pada auto complete text pada handphone atau search kata pada google muncul rujukan - rujukan kata.

Contoh spa, space, speak, spade, dll. memiliki awal kata yang sama yaitu s dan p, lalu memiliki berbagai cabang anak hingga terbentuk kata.

Tries pada umumnya terdiri dari character untuk membentuk suatu kata. Tries memiliki map(character dan triesnya, bercabang - cabang lagi). Untuk menandakan terbentuk suatu kata, memberi tahu akhir suatu kata digunakan bool is end. Contoh bool is end memberi tahu bahwa ada sebuah kata "spa" dan "space".

Sumber:
Binus Lecture
http://hardiyanticitrawati1901527971.blogspot.com/2016/05/dalam-pertemuan-kali-ini-kami-membahas.html
https://slideplayer.com/slide/3906274/
https://www.geeksforgeeks.org/heap-data-structure/
https://venus.cs.qc.cuny.edu/~mfried/cs313/priority_queues_heaps.html
https://stackoverflow.com/questions/53888694/try-to-understand-delete-min-of-min-max-heap