Heap & Tries

Heap & Tries

Heap adalah sebuah tree yang dimana inputannya berurut sesuai array. Pada dasarnya konsep heap memakai konsep tree, namun dalam heap memiliki beberapa jenis yaitu:

1. Min Heap
2. Max Heap
3. Min-Max Heap

Min Heap

Mengapa disebut min heap? Dikarenakan parent pada heap memiliki nilai yang lebih kecil daripada childrennya. Kita lihat contohnya sebagai berikut:

Array : 1,2,3,17,19,36,7,25,100

Bentuk tree seperti ini karena insert dalam heap diurutkan dari kiri ke kanan, dan pada heap tidak ada array[0] hal itu dilakukan untuk mempermudah proses insert node.

Untuk mencari parent/children dari sebuah node bisa digunakan rumus berikut:

Mencari Parent : idxNode/2

Mencari children left : idxNode*2

Mencari children right : (idxNode*2)+1

Sebagai contoh kita ambil node '2' yang memiliki index 2

Parent Node 2 : 2/2 = 1 (index ke -1, yaitu node 1)

Children Left : 2*2 = 4 (index ke - 4 , yaitu node 17)

Children Right : 2*2 + 1 = 5 (index ke - 5 , yaitu node 19)

Ketika insertion, node baru yang dimasukkan ternyata lebih kecil dari parentnya maka akan dibandingkan antara node baru dengan parent jika node baru lebih kecil akan ditukar.

Contoh jika kita input angka baru yaitu angka 4. Node ini akan tersambung sebagai children left dari angka 19, dan karena angka 4 ini lebih kecil dari parentnya yaitu 19, maka angka 4 ditukar dengan angka 19. Lalu dilihat lagi apakah angka 4 lebih kecil dari angka 2, ternyata tidak jadi tidak perlu ditukar. 

Lalu untuk delete, misalkan kita ingin delete node 2. Selalu diambil array terakhir sebagai pengganti, yang disini adalah node 100.

Kita bandingkan dengan tiap children dari node 100 yaitu 17 dan 19 manakah yang lebih kecil. 17 lebih kecil jadi kita tukar 100 dengan 17. 

Kita bandingkan lagi dengan childrennya yaitu 25. 25 lebih kecil dari 100 sehingga ditukar lagi.

Max Heap

Sama dengan min heap kali ini node parent harus memiliki nilai yang lebih besar daripada childrennya.

Contoh :

Array : 90,89,70,36,75,63,65,21,18,15

Konsep Insert dan deletenya pun sama dengan Min Heap. Yang berbeda pada insert dilihat apakah children lebih besar dari parentnya, jika iya aka di swap. 

Min Max Heap

Lalu yang terakhir ada min max heap. Heap ini merupaka campuran dari min dan juga max heap karena pada heap ini memiliki level-level seperti berikut.

Pada level genap terdapat nilai minimum dan pada level ganjil terdapat nilai maximum. Setiap insert dilakukan kita harus cek parentnya terdapat pada level apa jika parentnya min, makan node baru kita harus lebih besar dari parent dan sebaliknya.

Tries

Tries bentuknya juga memakai konsep tree, namun pada tries hanya menyimpan sebuah karakter dan biasanya digunakan untuk auto-complete kata-kata.

Contoh bentuk Tries:

                       root
                    /   \    \
                    t   a     b
                    |   |     |
                    h   n     y
                    |   |  \  |
                    e   s  y  e
                 /  |   |
                 i  r   w
                 |  |   |
                 r  e   e
                        |
                        r

Dimulai dari root bisa membentuk berbagai kata sesuai alur tree yang ada.

Seperti "answer","any","bye","there","their".