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 :
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 :
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 :
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
