HEAP & TRIES

BINARY HEAP AND TRIES 
APA ITU ? 

A. Binary Heap Overview

--------------------------------------------------------------------------------------------------------------------------

Apa itu Binary Heap ? Binary Heap adalah suatu struktur data berbentuk tree ( terapan BST ) yang dinamis karena penggunaan yang bergantung dengan fungsionalitas kondisinya.

Nah , sebenarnya jenis kondisional Binary Heap itu ada tiga guys !

Yuk , kita simak satu per satu !

1) MIN - HEAP 

Misalkan kita akan menginput suatu data secara random . Anggaplah inputnya :

35 33 42 10 14 19 27 44 26 31

Nah , maka format MIN-HEAP nya akan seperti ini :

Loh kok bisa begitu , min ? Nah urutan masuknya sebenarnya yang membuat algoritma MIN-HEAP  bekerja . 

Binary Heap akan menginsert data dengan format : root - kiri - kanan --> left side ( kiri-kanan) --> right side ( kiri-kanan) dan akan berlanjut seperti itu terus .

Seperti ini jika digambarkan :

Nah , maka setelah sudah di "sort" , kita dapat mensort value data heap dimana child yang terdalam akan memiliki value terbesar , dan root treenya adalah nilai paling kecil . Inilah implementasi MIN-HEAP.

Dari animasi di atas , maka value 3 dan 2 akan dibandingkan dengan parentnya yakni 6 , dan dipilih yang terkecil , yakni data 2 . Maka 6 akan ditukar dengan 2 . Hal yang sama dilakukan di sebelah kanan dimana nilai 8 ditukar dengan 1 . Pada depth 2 , dipilih nilai paling kecil yakni 1 sehingga 10 ( root ) ditukar dengan nilai 1. Karena depth 2 nilai data 10 lebih besar daripada subtree kirinya yakni 8 , maka ditukar kembali.

2) MAX - HEAP

Implementasi MAX-HEAP sama seperti MIN-HEAP  guys ! Hanya saja , sekarang karena MIN-HEAP ter-"sort" secara ascending ke bawah , maka MAX-HEAP ter-"sort" secara descending ke bawah . Ini mengakibatkan root tree heap adalah nilai dengan data TERBESAR .

Mari kita simak secara lengkapnya seperti ini :

3) MIN-MAX HEAP

Waduh , tadi sudah ada min dan max-heap . Kok sekarang digabung ? Yup , penggabungan min-max heapnya dilihat dari depth treenya. Depth ganjil akan menggunakan terapan min heap  sedangkan Depth genap akan menggunakan max-heap .

4) DELETION IN MIN/MAX-HEAP

Nah , perlu diketahui , data yang selalu dihapus pada Binary Heap itu node root nya lho ! Aneh ya ? Tapi ada alasannya kok . Aturan deletion masih mengikuti aturan BST , namun data yang akan menggantikan node root adalah DATA TERAKHIR yang terinput . 

Untuk simulasinya , agar kalian semua mengerti , yuk simak gambar berikut ! 

Gambar tersebut adalah contoh DELETION PADA MAX-HEAP .

Node root 44 dihapus digantikan oleh node data terakhir yakni node data 14. Lalu node data root 14 akan dibandingkan pada node 42 ( dibawahnya , yang paling besar dari 35 atau 42 , yakni 42 ). Node 14 pun ada di depth 2 , dan dibandingkan kembali oleh data node 33 lalu ditukar posisinya . Dan terakhir , node data 26 ditukar dengan node 14. 

--------------------------------------------------------------------------------------------------------------------------

B. TRIES

Apa itu Tries ? Apakah mirip dengan tree lagi ?

YUP . Tapi kali ini , data yang dimasukkan bukan dalam bentuk integer guys . TAPI CHAR . 

Kalian pasti pernah main game sambung kata kan ? Nah implementasi Tries mirip dengan game sambung kata , hanya saja berbentuk tree .

Nah , itu saja quick introduction heap & tries untuk kalian ^0^ . Terima kasih !

Sumber yang dipakai :
https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm
https://www.cs.usfca.edu/~galles/visualization/Heap.html
https://www.geeksforgeeks.org/trie-insert-and-search/