Heap & Tries

1. Heap

Heap merupakan konsep binary tree yang memiliki 3 tipe:

a. Min Heap

Heap ini akan memiliki root yang valuenya paling kecil diantara semua node yang ada. Ketika insertion, setiap node baru akan mengecek apakah parentnya lebih besar atau lebih kecil. Jika parent lebih besar maka node akan ditukar tempatnya dengan parent dan pengecekan akan terus dilakukan sampai value dari parent lebih kecil dari value node yang diinsert. Ketika deletion, node paling terakhir yang akan menggantikan root lalu akan dilakukan pengecekan dengan left dan right child lalu yang lebih kecil akan ditukar posisinya dengan root. Pengecekan akan terus dilakukan sampai node yang sebelumnya menggantikan root sudah memiliki value yang lebih kecil dari kedua childnya.

b. Max Heap

Heap ini memiliki root yang valuenya paling besar diantara semua node yang ada. Berbeda dengan min heap, node baru akan terus ditukar dengan parentnya selama node memiliki value yang lebih besar dibanding parentnya. Ketika deletion, node paling terakhir yang akan menggantikan root lalu akan dilakukan pengecekan dengan left dan right child lalu yang lebih besar akan ditukar posisinya dengan root. Pengecekan akan terus dilakukan sampai node yang sebelumnya menggantikan root sudah memiliki value yang lebih besar dari kedua childnya.

Contoh min dan max heap:

c. Min-Max Heap

Heap yang memiliki level dimana level genap akan memiliki nilai min dan level ganjil akan memiliki nilai max.

Contoh:

2. Impelementasi Heap

Contoh implementasi heap adalah heap sort, dimana ada dua tipe dari heap sort.

- Min Heap Sort(Ascending)

- Max Heap Sort(Descending)

Kedua proses sorting sama, yaitu dengan menghapus dan menginsert root ke array baru. Ketika min heap sort, root akan selalu berupa nilai minimum dari semua node yang ada sehingga akan membuat sort ascending, sedangkan max heap sort, root akan selalu memiliki nilai yang paling maksimum diantara semua node sehingga akan membuat sort descending.

3. Tries

Tries merupakan tree yang bisa memiliki child berapapun. Tries sendiri sering digunakan pada game bubble words atau autocomplete pada searching. Tries akan memiliki root yang berupa suatu karakter yang tidak akan digunakan sama sekali dalam membentuk suatu kata (bisa juga dikosongkan). Hal ini dilakukan agar ketika membentuk suatu kata kita tidak terlimitasi dengan kata yang memiliki satu huruf yang sama saja. Tries akan memiliki boolean isEnd pada setiap nodenya yang akan menandakan apakah huruf-huruf tersebut akan membentuk suatu kata atau tidak.

Referensi:

- https://www.geeksforgeeks.org/heap-data-structure/ (Min and Max Heap)

- https://stackoverflow.com/questions/14332279/delete-max-operation-in-a-min-max-heap (Min-Max Heap)