Heap & Tries
Heap
Apa sih heap itu? Heap adalah sebuah binary tree komplit data structure yang memenuhi properti-properti dari heap itu sendiri. Node-node yang merupakan node dari heap terurut dengan urutan tertentu. Heap sendiri memiliki beberapa jenis, apa saja?
- Minimum Heap
- Maximum Heap
- Min-Max Heap
Pada dasarnya semua heap itu sama. Pembedanya hanya ada pada letak urutan node nya.
Apa sih heap itu? Heap adalah sebuah binary tree komplit data structure yang memenuhi properti-properti dari heap itu sendiri. Node-node yang merupakan node dari heap terurut dengan urutan tertentu. Heap sendiri memiliki beberapa jenis, apa saja?
- Minimum Heap
- Maximum Heap
- Min-Max Heap
Pada dasarnya semua heap itu sama. Pembedanya hanya ada pada letak urutan node nya.
1. Minimum Heap
Urutan minimum heap ini yakni nilai node yang paling kecil berada di root nya. Sementara susunan node ke bawah nya itu berdasarkan besar-kecil nilai node nya. Node yang memiliki nilai paling besar/maximum pasti selalu berada di bagian leaf node tree ini. Bisa kita lihat pada gambar di bawah ini:
Gambar di atas menunjukkan bahwa nilai node yang menjadi root dari minimum heap ini merupakan node yang memiliki nilai terkecil di antara semua nilai node-node yang lainnya. Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika kita menggunakan array saat meng-implementasikannya.
Berikut adalah step simulasi dalam menyusunan minimum heap hingga urutannya benar:
Dibawah ini adalah step simulasi untuk insert new node ke dalam minimum heap:
Dibawah ini adalah step simulasi untuk deletion node yang akan kita hapus pada minimum heap:
Gambar di atas menunjukkan bahwa nilai node yang menjadi root dari minimum heap ini merupakan node yang memiliki nilai terkecil di antara semua nilai node-node yang lainnya. Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika kita menggunakan array saat meng-implementasikannya.
Berikut adalah step simulasi dalam menyusunan minimum heap hingga urutannya benar:
Dibawah ini adalah step simulasi untuk insert new node ke dalam minimum heap:
Dibawah ini adalah step simulasi untuk deletion node yang akan kita hapus pada minimum heap:
2. Maximum Heap
Pada dasarnya, bentuk dari maximum heap ini hampir sama dengan minimum heap, namun yang membedakannya terletak pada nilai node root dari treenya. Urutan maximum heap ini yakni nilai node yang paling besar berada di root nya. Sementara susunan node ke bawah nya itu berdasarkan besar-kecil nilai node nya. Node yang memiliki nilai paling kecil/minimum pasti selalu berada di bagian leaf node tree ini. Bisa kita lihat pada gambar di bawah ini:
Gambar di atas menunjukkan bahwa nilai node yang menjadi root dari maximum heap ini merupakan node yang memiliki nilai terbesar di antara semua nilai node-node yang lainnya. Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika kita menggunakan array saat meng-implementasikannya, sama seperti minimum heap.
Berikut adalah step simulasi dalam menyusunan maximum heap hingga urutannya benar:
Dibawah ini adalah step simulasi untuk insert new node ke dalam maximum heap:
Dibawah ini adalah step simulasi untuk deletion node yang akan kita hapus pada maximum heap:
Pada dasarnya, bentuk dari maximum heap ini hampir sama dengan minimum heap, namun yang membedakannya terletak pada nilai node root dari treenya. Urutan maximum heap ini yakni nilai node yang paling besar berada di root nya. Sementara susunan node ke bawah nya itu berdasarkan besar-kecil nilai node nya. Node yang memiliki nilai paling kecil/minimum pasti selalu berada di bagian leaf node tree ini. Bisa kita lihat pada gambar di bawah ini:
Gambar di atas menunjukkan bahwa nilai node yang menjadi root dari maximum heap ini merupakan node yang memiliki nilai terbesar di antara semua nilai node-node yang lainnya. Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika kita menggunakan array saat meng-implementasikannya, sama seperti minimum heap.
Berikut adalah step simulasi dalam menyusunan maximum heap hingga urutannya benar:
Dibawah ini adalah step simulasi untuk insert new node ke dalam maximum heap:
Dibawah ini adalah step simulasi untuk deletion node yang akan kita hapus pada maximum heap:
Berikut adalah step simulasi dalam menyusunan maximum heap hingga urutannya benar:
Dibawah ini adalah step simulasi untuk insert new node ke dalam maximum heap:
Dibawah ini adalah step simulasi untuk deletion node yang akan kita hapus pada maximum heap:
3. Min-Max Heap
Pada dasarnya, bentuk dari min-max heap ini hampir sama dengan minimum dan maximum heap, namun yang membedakannya terletak pada nilai node root dari treenya. Urutan min-max heap ini yakni nilai node yang paling kecil berada di root nya. Sementara susunan node ke bawah nya itu adalah nilai maximum, minimum, maximum, minimum, dan seterusnya. Nilai node yang akan terletak di paling bawah dari tree ini tidak dapt kita tentukan secara pasti, bisa jadi nilai paling kecil atau nilai paling besar. Hal ini tergantung pada banyaknya data yang kita peroleh. Bisa kita lihat pada gambar di bawah ini:
Pada min-max heap ini, nilainya akan terus bersilangan antara maksimum dan minimum nodenya. Secara keseluruhan bentuk insert dan deletion pada heap ini sama saja dengan minimum dan maximum heap. Namun, kita harus benar-benar teliti pada saat menyusun/menyelesaikan heap ini, karena sedikit tricky dan kita terkadang akan tertukar posisinya.
Pada dasarnya, bentuk dari min-max heap ini hampir sama dengan minimum dan maximum heap, namun yang membedakannya terletak pada nilai node root dari treenya. Urutan min-max heap ini yakni nilai node yang paling kecil berada di root nya. Sementara susunan node ke bawah nya itu adalah nilai maximum, minimum, maximum, minimum, dan seterusnya. Nilai node yang akan terletak di paling bawah dari tree ini tidak dapt kita tentukan secara pasti, bisa jadi nilai paling kecil atau nilai paling besar. Hal ini tergantung pada banyaknya data yang kita peroleh. Bisa kita lihat pada gambar di bawah ini:
Pada min-max heap ini, nilainya akan terus bersilangan antara maksimum dan minimum nodenya. Secara keseluruhan bentuk insert dan deletion pada heap ini sama saja dengan minimum dan maximum heap. Namun, kita harus benar-benar teliti pada saat menyusun/menyelesaikan heap ini, karena sedikit tricky dan kita terkadang akan tertukar posisinya.
Tries
Apa itu tries? Tries adalah suatu struktur data tree terurut yang digunakan untuk menyimpan array asosiatif. Kalian pasti tahu auto correct dan auto complete yang ada di keypad android kalian kan? Yang pas kita baru ketik beberapa huruf udah muncul kata yang ingin kita ketik ataupun yang bisa membenarkan kata kita apabila ada typo? Nah itu menggunakan tries ini.
Istilah TRIES berasal dari kata RETRIEVAL.
Fakta-Fakta Tentang Tries
- Tries adalah tree yang setiap simpulnya mewakili satu kata atau awalan dari sebuah kata.
- Root mewakili karakter kosong(" ") atau NULL.
Untuk lebih lanjut silahkan di lihat dan cermati gambar Tries dibawah....
Secara umum, penyusunan dari tries cukup simple dan mudah, kalian hanya tinggal melihat huruf pertama dari kata yang ingin kalian masukkan, apabila sudah ada huruf dari awalan kata kalian, maka selanjutnya kalian harus memeriksa huruf selanjutnya. Jika tidak ada lagi huruf yang sama, maka kalian tinggal memasukkan sisa huruf dari kata kalian di bawah huruf terakhir. Cukup simple dan mudah bukan?
Sekian...
Terima kasih ^_^
Apa itu tries? Tries adalah suatu struktur data tree terurut yang digunakan untuk menyimpan array asosiatif. Kalian pasti tahu auto correct dan auto complete yang ada di keypad android kalian kan? Yang pas kita baru ketik beberapa huruf udah muncul kata yang ingin kita ketik ataupun yang bisa membenarkan kata kita apabila ada typo? Nah itu menggunakan tries ini.
Istilah TRIES berasal dari kata RETRIEVAL.
Fakta-Fakta Tentang Tries
- Tries adalah tree yang setiap simpulnya mewakili satu kata atau awalan dari sebuah kata.
- Root mewakili karakter kosong(" ") atau NULL.
Untuk lebih lanjut silahkan di lihat dan cermati gambar Tries dibawah....
Secara umum, penyusunan dari tries cukup simple dan mudah, kalian hanya tinggal melihat huruf pertama dari kata yang ingin kalian masukkan, apabila sudah ada huruf dari awalan kata kalian, maka selanjutnya kalian harus memeriksa huruf selanjutnya. Jika tidak ada lagi huruf yang sama, maka kalian tinggal memasukkan sisa huruf dari kata kalian di bawah huruf terakhir. Cukup simple dan mudah bukan?
Sekian...
Terima kasih ^_^
Referensi :
- https://www.hackerearth.com/practice/data-structures/trees/heapspriority-queues/tutorial/
- https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm
- https://www.geeksforgeeks.org/deletion-binary-tree/
- https://www.geeksforgeeks.org/insertion-and-deletion-in-heaps/
- https://www.slideshare.net/HoangNguyen446/heaps-61679009
- https://www.geeksforgeeks.org/trie-insert-and-search/
- https://allcprogrammingandalgorithm.wordpress.com/heap-sort/
- https://www.ques10.com/p/4168/sort-the-following-data-in-descending-order-usin-1/
- https://stackoverflow.com/questions/14332279/delete-max-operation-in-a-min-max-heap
