Heap and Tries

Heap

Heap sort adalah sebuah metode sorting (pengurutan) angka pada sebuah array dengan cara menyerupai binary tree, yaitu dengan cara memvisualisasikan sebuah array menjadi sebuah binary tree yang nantinya pada binary tree tersebut nilai pada masing-masing index array akan diurutkan. Heap tree terbagi menjadi 2 jenis yaitu Max-Heap dan Min-Heap, dimana max-heap adalah kondisi heap tree yang memiliki nilai tertinggi berada di node root dan setiap child node memiliki nilai yang lebih kecil dari nilai yang dimiliki parent nodenya. Sedangkan pada min-heap adalah kondisi kebalikan dengan max-heap, pada min-heap nilai terkecil berada di node root dan setiap child node memiliki nilai yang lebih besar dari nilai yang dimiliki parent nodenya. Kemudian ada pula yang diberi nama Min-Max Heap yaitu min-heap dan max-heap levelnya saling bergantian pada tree

Min Heap

Di dalam konsep Min Heap, node yang berada dibawahnya atau parent nilainya akan lebih kecil dibandingkan dengan node anaknya. Maka dapat disimpulkan node root merupakan node dengan nilai paling kecil , dan salah satu node dari leaf node merupakan node yang nilainya paling besar.

Max Heap

Konsep Max Heap hanya berbeda sedikit , perbedaannya hanya ada di node paling atas akan memiliki node dengan nilai terbesar dan salah satu node dari leaf node akan memiliki nilai yang terkecil.
Data Structures: Heap & Deap

Min-Max Heap

Konsep Min Max Heap adalah level root akan bernilai minimum, selanjutnya akan bernilai maximum, dan seterusnya. Nilai terkecil berada di root dan nilai terbesar berada di salah satu node pada level setelah root. Level min hanya dapat dibandingkan dengan level min, dan sebaliknya.

Tries

Tries atau prefix tree adalah suatu pohon struktur data yang terurut yang menyimpan data array, biasanya string. Tries sudah diterapkan ke banyak hal dalam kehidupan sehari-hari, contohnya pada web browser. suatu web browser dapat mengira atau mensugestikan kata-kata yang mungkin kita maksud saat kita mengetik huruf pertamanya saja atau kita lebih mengenalnya dengan auto complete.Tries adalah suatu tree dimana setiap vertex/pathnya menggambarkan suatu kata, rootnya kosong.

Komentar

Postingan populer dari blog ini

Final Review

Data Structure 3 Maret 2020

Linked List II