Summary Heap
Pada Video Conference kita mempelajari tentang Heap dan Tries
Heap merupakan suatu binary tree yang complete yang menggunakan property dari heap, Heap ini dibagi menjadi dua macam yaitu Min Heap dan Max Heap.
Min Heap berarti setiap node atau parent lebih kecil dari children mereka, sehingga binary tree yang akan terbuat tersusun dari yang terkecil hingga terbesar dari atas.
Max Heap berarti seiap node atau parent lebih besar dari children mereka, sehingga binary tree yang akan terbuat tersusun dari yang terbesar hingga terkecil dari atas.
Kita juga mempelajari cara insert kedalam Heap, untuk insert kedalam min atau max menggunakan cara yang sama. Apabila kita menginsert suatu element baru maka node itu akan masuk kedalam index terakhir atau leaf terujung, lalu kita harus cek apakah elemen baru lebih kecil atau lebih besar dari parentnya apabila lebih kecil untuk min heap maka element baru akan bertukar posisi dengan parentnya dan kebalikannya juga dengan max heap apabila lebih besar dari parentnya maka element baru akan bertukar posisi dengan parentnya. Proses ini akan dilakukan sampai element baru tersebut tidak lebih besar atau lebih kecil dari parentnya.
Apabila untuk delete, hanya dapat terjadi pada root. Delete dilakukan dengan mengganti root dengan last element dari Heap, dan akan dilakukan pengecekkan ke bawah apakah lebih besar atau lebih kecil dari childrennya (kebalikkan dari insert).
Selain Min Heap dan Max Heap terdapat juga Min-Max Heap, Heap ini merupakan gabungan dari min dan max yang berarti posisi min dan max akan berubah setiap levelnya untuk contoh lihatlah gambar dibawah.
Pada Heap ini element terkecil akan terletak di root dan element terbesar akan terletak di children salah satu dari root. Untuk cara insert hampir sama dengan min dan max Heap, element baru akan dimasukkan ke element terakhir dan pengecekkan dilakukan tidak hanya terhadap parent, tetapi juga terhadap grandparentnya apabila parent tidak memenuhi syarat. Untuk delete juga sama tetapi dapat dilakukan selain pada root.
Pemakaian Heap dapat diimplementasikan seperti Heap sort, Selection untuk mencari max dan min, dan Graph Algorithms.
Tries merupakan suatu binary search tree yang menyimpan beberapa keys yang dapat diakses. Biasa digunakan untuk search algorithm atau autofill.
Heap merupakan suatu binary tree yang complete yang menggunakan property dari heap, Heap ini dibagi menjadi dua macam yaitu Min Heap dan Max Heap.
Min Heap berarti setiap node atau parent lebih kecil dari children mereka, sehingga binary tree yang akan terbuat tersusun dari yang terkecil hingga terbesar dari atas.
Max Heap berarti seiap node atau parent lebih besar dari children mereka, sehingga binary tree yang akan terbuat tersusun dari yang terbesar hingga terkecil dari atas.
Kita juga mempelajari cara insert kedalam Heap, untuk insert kedalam min atau max menggunakan cara yang sama. Apabila kita menginsert suatu element baru maka node itu akan masuk kedalam index terakhir atau leaf terujung, lalu kita harus cek apakah elemen baru lebih kecil atau lebih besar dari parentnya apabila lebih kecil untuk min heap maka element baru akan bertukar posisi dengan parentnya dan kebalikannya juga dengan max heap apabila lebih besar dari parentnya maka element baru akan bertukar posisi dengan parentnya. Proses ini akan dilakukan sampai element baru tersebut tidak lebih besar atau lebih kecil dari parentnya.
Apabila untuk delete, hanya dapat terjadi pada root. Delete dilakukan dengan mengganti root dengan last element dari Heap, dan akan dilakukan pengecekkan ke bawah apakah lebih besar atau lebih kecil dari childrennya (kebalikkan dari insert).
Selain Min Heap dan Max Heap terdapat juga Min-Max Heap, Heap ini merupakan gabungan dari min dan max yang berarti posisi min dan max akan berubah setiap levelnya untuk contoh lihatlah gambar dibawah.
Pada Heap ini element terkecil akan terletak di root dan element terbesar akan terletak di children salah satu dari root. Untuk cara insert hampir sama dengan min dan max Heap, element baru akan dimasukkan ke element terakhir dan pengecekkan dilakukan tidak hanya terhadap parent, tetapi juga terhadap grandparentnya apabila parent tidak memenuhi syarat. Untuk delete juga sama tetapi dapat dilakukan selain pada root.
Pemakaian Heap dapat diimplementasikan seperti Heap sort, Selection untuk mencari max dan min, dan Graph Algorithms.
Tries merupakan suatu binary search tree yang menyimpan beberapa keys yang dapat diakses. Biasa digunakan untuk search algorithm atau autofill.
Comments
Post a Comment