Heap
Apa itu Heap? Heap merupakan Data Structure yang menggunakan konsep Binary Tree yang tersimpan dalam bentuk array dalam urutan yang spesifik. Jumlah anak maksimal yang dimiliki oleh heap bergantung pada tipe heap itu sendiri. Pada umumnya, anak maksimalnya adalah dua. Saat melakukan input, input baru akan menjadi node paling akhir dari sebuah heap. Kemudian, akan dilakukan adjustment agar sesuai dengan aturan heap. Heap memiliki 3 bentuk, yaitu min heap, max heap, dan min-max heap.
Min Heap, Max Heap, Min-Max Heap
Min heap dan max heap memiliki cara kerja yang sama, bedanya pada saat melakukan adjustment min heap akan membandingkan apabila child (input baru) lebih kecil dari parent, maka dia akan melakukan swap dengan parentnya. Sedangkan max heap akan membandingkan apabila child lebih besar dari parent, maka dia akan melakukan swap dengan parentnya. Oleh karena itu, root dari min heap selalu angka yang paling kecil dan root dari max heap selalu angka yang paling besar.
Untuk min-max heap, pada tiap level tree memiliki status yang berbeda. Untuk level ganjil akan memiliki status min dan untuk level genap akan memiliki status max.
Insertion
Bagaimana cara memasukkan data ke dalam heap? Pertama-tama, data yang ingin dimasukkan akan menjadi node terakhir dalam heap (tiap level akan dipenuhi dulu setelah level tersebut tidak bisa menampung node lagi, maka akan membuat level baru). Node baru tersebut bisa jadi melanggar aturan heap (baik heap min, max, maupun min-max). Oleh karena itu, ia akan dibandingkan dengan parent (apabila heap min atau max) atau bahkan dibandingkan dengan grandparent juga (heap min-max). Apabila setelah dibandingkan, ternyata memang melanggar aturan tersebut, maka akan dilakukan adjustment yang dinamakan heapify up karena dibandingkan dengan node atasnya (parent maupun grandparent).
Deletion
Jika kita sudah tau bagaimana cara memasukkan data kedalam heap, maka kita juga harus belajar bagaimana cara menghapus data dari heap. Ketika akan menghapus dari heap. Maka yang kita hapus adalah root nya. Tidak peduli apakah itu heap min, heap max, ataupun heap min-max. Setelah itu, node paling akhir akan menjadi node, dan akan dilakukan adjustment yang dinamakan heapify down karena dibandingkan dengan node bawahnya. Lalu, bagaimana jika kita ingin menghapus node tertentu secara spesifik? Hal tersebut dapat dilakukan dengan melakukan searching lalu hapus node tersebut. Akan tetapi, hal tersebut berbeda dengan heap yang kita sebutkan tadi. Heap yang dapat menghapus node tertentu dapat disebut modified heap.
Tries
Apa itu Tries? Tries adalah tree data structure yang berurutan yang digunakan untuk menyimpan string dalam array. Tries berasal dari kata “retrieval” karena tries dapat menemukan 1 kata dari kamus hanya dengan menggunakan prefix. Apa gunanya tries? Tries dapat digunakan sebagai spell checker atau suggestion words seperti pada google atau keyboard pada hp karena tries menggunakan prefix dari yang kita inputkan.
Bagian root tidak memiliki nilai atau NULL. Serta untuk mengetahui bahwa huruf terakhir akan membentuk sebuah kata, maka trie memiliki boolean variable yang disebut dengan IsEnd (dalam gambar, bintang merupakand IsEnd). Contohnya dari node “d”, akan membentuk kata “do” apabila berhenti di “o” dan akan membentuk kata “dork” apabila berhenti di node “k”.
References
