Heap dan Tries

Heap and Tries

Heap itu pada dasarnya adalah BST (Binary Search Tree) yang memenuhi psayarat dari properti heap. Heap juga dapat dibilang implementasi efisien dari tipe abstrak dengan antrian prioritas.

Ada 3 tipe heap, yaitu :

Min Heap

Dalam min heap, setiap node di atas lebih kecil dari pada childrennya. Contohnya seperti dibawah ini,

Untuk insert, urutannya selalu dari kiri baru ke kanan. Sebagai contoh apabila di insert angka 14 maka seperti dibawah ini,

Untuk deletion, nilai terakhir dinakkan ke atas dan melakukan heapifi apabila lebih kecil, sebagi contoh apabila root dihapus maka seperti ini,

Max Heap

Max hepa adalah kebalikan daripada min heap, Jadi node yang diatas lebih besar daripada childrennya, contohnya seperti berikut ini,

Untuk insert sama seperti min heap semuanya dimulai dari sebalah kiri, sebagai contoh apabila di insert angka 2 maka jadi seperti,

Untuk deletiosn juga sama seperti min heap jadi apabila di hapus rootnya maka angka terakhirnya naik menggantikan root dan heapifi apabila childrennya ada yang lebih besar. Sebagai contoh apabila root nya dihapus menjadi,

Min-Max Heap

Min max heap adalah gabungan dari min heap dan max heap,  jadi bagian paling atas itu adalah min heap  dan children dari min heap tersebut adalah max heap dan seterusnya.

Untuk insert min max heap dimulai dari sebelah kiri seperti biasa tetapi abis itu dilakukan heapifi agar urutannya tidak salah. Sebagai contoh apabila di insert angka 49 maka akan di cek ke grand parentnya apakah lebih besar atau tidak, karena 50 lebih besar dari 34 maka di tukar tempatnya. Karena tidak ada grand parent lagi maka sudah selesai. Contoh treenya seperti dibawah ini

Untuk delete sama seperti heap lainnya, apabila masih belum urut maka dilakukan heapifi. Jadi apabila kita ingin menghapus angka terbesar yaitu 49, maka angka terakhir yaitu 34 ditukar dengan 49. Karena sudah urut dan tidak merusak syarat dan properti min max heap maka sudah selesai. Jadi treenya menjadi seperti berikut ini,

Tries

Tries adalah tree yang digunakan untuk menyimpan set yang dinamis atau associative array, biasanya berupa string. Dapat lebih efektif dan juga efisien. Tries itu biasanya digunakan dalam game-game bubble words. Contoh tries adalah sebagai berikut,