Heap & Tries

Heap

Heap adalah suatu struktur binary tree yang lengkap dan memiliki beberapa sifat tertentu yang mengimplementasikan priority queue, diimplementasikan bisa menggunakan linked-list, namun lebih mudah menggunakan array.

Penggunaan heap dibagi menjadi 3 tipe yaitu :
1. Min Heap
2. Max Heap
3. Min-Max Heap

Masing-masing heap memiliki cara insertion dan delete yang berbeda-beda dan beberapa perbedaan logic yang terbalik-balik


1. Min Heap

Pada pohon Min Heap, elemen paling kecil terletak pada root, dan elemen paling besar terletak pada salah satu node leave yang ada.
Contoh Min Heap :

Parent akan lebih kecil daripada childrennya, serta tidak ada hubungannya dengan unclenya.

Insertion : Bila memasukkan sebuah angka baru, maka dimasukkan ke node paling akhir, lalu bandingkan dengan parentnya. Jika parent lebih besar bisa lakukan swap, jika parent lebih kecil maka sudah benar.
Delete : Root dihilangkan lalu diganti dengan angka dari node terakhir lalu bandingkan. Jika children lebih kecil maka tukar sampai root adalah angka terkecil.

2. Max Heap

Pada pohon Max Heap, elemen paling besar terletak pada root, dan elemen paling kecil terletak pada salah satu node leave yang ada.
Contoh Max Heap :

Parent akan lebih besar daripada childrennya, serta tidak ada hubungannya dengan unclenya.

Insertion : Bila memasukkan sebuah angka baru, maka dimasukkan ke node paling akhir, lalu bandingkan dengan parentnya. Jika parent lebih kecil bisa lakukan swap, jika parent lebih besar maka sudah benar.
Delete : Root dihilangkan lalu diganti dengan angka dari node terakhir lalu bandingkan. Jika children lebih besar maka tukar sampai root adalah angka terbesar.

3. Min-Max Heap

Merupakan gabungan dari Min Heap dan Max Heap menjadi suatu heap yang unik. Urutannya selalu Min, lalu Max, lalu Min dan seterusnya. Level genap adalah Min, level ganjil adalah Max.
Contoh Min-Max Heap :

Insertion dan Delete sama seperti Min Heap dan Max Heap, tapi harus memperhatikan levelnya mana yang harus Max dan mana yang harus Min.


Tries

Tries adalah pohon struktur data yang terurut dan menyimpan karakter. Di gunakan untuk auto complete, searching, bubble words dll.
Contoh tries :

Kata bisa menjadi:
ASSOC
ALGO
ALL
ALSO

TRIE
TREE