Heap and Tries

HEAP

Heap adalah complete binary tree berdasarkan struktur data yang memenuhi properti heap. Tujuan dari heap ini adalah untuk menemukan nilai terkecil pada min heap dan nilai terbesar pada max heap. Penulisan heap mirip dengan BST, namun pada heap, anak kiri tidak ada hubungannya dengan anak yang kanan. Heap dapat diimplementasikan menggunakan linked-list, tetapi jauh lebih mudah untuk mengimplementasikan Heap menggunakan array sehingga setiap elemen yang baru masuk ke array pada index terakhir yang kosong.

Secara umum, ada dua jenis heap:
1. Min Heap 

Setiap nilai elemen node lebih kecil daripada elemen anaknya (child). Dapat dilihat bahwa nilai elemen terkecil berada pada root dan elemen terbesar berada pada salah satu leaves node. Contoh min heap:

Insertion pada Min Heap

Saat melakukan insertion, kita harus mempertahankan properti heapnya. Pertama, memasukkan elemen baru ke akhir heap (setelah index elemen terakhir). Lalu, unheap elemen baru tersebut dan memperbaiki properti heapnya, misalnya pada min heap jika elemen baru lebih kecil dari rootnya maka posisinya harus ditukar, namun jika lebih besar maka properti heap sudah benar. Contoh:

- Insert (20)

- Insert (5)

Deletion pada Min Heap

Pada deletion, kita hanya memperhatikan deletion pada elemen terkecil yang terletak pada root. Pertama, ganti root dengan elemen terakhir dari heap. Lalu mengurangi jumlah elemen dalam heap. Setelah itu melakukan downheap (memperbaiki posisi heap). Proses downheap dilakukan dengan membandingkan current node dengan nilai anak kiri dan kanan lalu menukar current node dengan anak terkecil. Proses ini dilakukan terus sampai current node lebih kecil dari nilai anaknya atau saat current node adalah leaf (tidak memiliki anak). Contoh:

- Delete (7)

2. Max Heap

Setiap nilai elemen node lebih besar daripada elemen anaknya (child). Dapat dilihat bahwa nilai elemen terbesar berada pada root dan elemen terkecil berada pada salah satu leaves node. Contoh max heap:

Insertion pada Max Heap

Saat melakukan insertion, kita harus mempertahankan properti heapnya. Pertama, memasukkan elemen baru ke akhir heap (setelah index elemen terakhir). Lalu, unheap elemen baru tersebut dan memperbaiki properti heapnya, misalnya pada max heap jika elemen baru lebih besar dari rootnya maka posisinya harus ditukar, namun jika lebih kecil maka properti heap sudah benar. Contoh:

- Insert (15)

Deletion pada Max Heap

Pada deletion, kita hanya memperhatikan deletion pada elemen terbesar yang terletak pada root. Pertama, ganti root dengan elemen terakhir dari heap. Lalu mengurangi jumlah elemen dalam heap. Setelah itu melakukan downheap (memperbaiki posisi heap). Proses downheap dilakukan dengan membandingkan current node dengan nilai anak kiri dan kanan lalu menukar current node dengan anak terbesar. Proses ini dilakukan terus sampai current node lebih besar dari nilai anaknya atau saat current node adalah leaf (tidak memiliki anak). Contoh:

- Delete (20)

MIN MAX HEAP

Min Max Heap merupakan gabungan dari min heap dan max heap. Kondisi heap bergantian antara min heap dan max heap pada setiap level. Setiap elemen pada tingkat genap/ganjil lebih kecil dari semua anak-anaknya berarti min level. Sedangkan, max level berarti setiap elemen pada level ganjil/genap lebih besar dari semua anak-anaknya.

Tujuan dari Min Max Heap adalah memungkinkan kita untuk menemukan elemen heap yang terkecil dan terbesar pada waktu yang sama.  

Pada Min Max Heap, elemen terkecil terletak pada root. Elemen terbesar terletak di salah satu anak root (kiri atau kanan). Elemen terbesar mungkin terletak pada root jika hanya ada satu elemen pada heap.

Insertion

1. Insert node baru pada index selanjutnya (setelah index terakhir)

2. Jika node baru tersebut terletak pada level min, maka bandingkan dengan parentnya.

- Jika parent < node maka swap dan upheapmax dari parentnya (lalu dibandingkan dengan grandparentnya dari posisi node setelah swap)

- Jika parent > node maka upheapmin dari posisi node (lalu dibandingkan dengan grandparentnya dari posisi node).

3. Jika key terletak pada level max :

- Jika parent > node maka swap dan upheapmin dari parentnya (lalu dibandingkan dengan grandparentnya dari posisi node setelah swap)

- Jika parent < node, upheapmax dari posisi node (lalu dibandingkan dengan grandparentnya dari posisi node)

Contoh:
- Insert (50)

>Upheapmin : 50 is larger than its parent, so do upheapmax
>Upheapmax : 50 is larger than its grand-parent, so swap their value

> Upheapmax : because node 50 doesn’t have grand-parent, the process is finished

Deletion
Ada dua jenis deletion pada Min Max Heap, yaitu delete min, dan delete max
- Delete Min = menghapus node terkecil, yaitu root
- Delete Max = menghapus node terbesar, yaitu salah satu dari anak root

Konsep deletenya sama seperti heap biasanya, yaitu node yang dihapus digantikan oleh node index terakhir lalu lakukan downheapmin jika delete min, atau downheapmax jika delete max.

Contoh:
- Delete Max

> Replace the max value and replace it with last node (14)

> Downheapmax : find the largest value from its children and grand-children. After that, swap their value.

> Downheapmax : because 14 parents is larger than 14, swap their value and continue downheapmax.

> Because 28 doesn’t have children or grand-children, the process is finished

TRIES

Tries atau Prefix Tree adalah ordered tree pada struktur data yang digunakan untuk menyimpan array asosiatif (biasanya string). Istilah trie berasal dari kata retrieval (pengambilan) yang berarti mencoba menemukan satu kata dalam kamus hanya dengan awalan kata saja / prefix word. Tries merupakan sebuah tree di mana setiap vertex mewakili satu kata atau awalan. Root mewakili karakter kosong (").

Contoh tries tersebut mengandung kata-kata:
1. ALGO
2. API
3. BOM
4. BOS
5. BOSAN
6. BOR

Tries biasanya digunakan untuk autocomplete pada saat searching di web. Tries juga digunakan untuk spell checker dan correction suggestion. Selain itu, ada beberapa game yang menggunakan konsep tries ini, salah satunya adalah Bubble Word.

Sumber:

1. PPT Binusmaya

2. https://sikisik.wordpress.com/struktur-data/

3. https://apalah-ini-itu.blogspot.com/2011/06/heap.html

4. https://suciantinovi.blogspot.com/2014/05/b-tree-and-heap-deap.html

Dibuat oleh:

Nama : Sheila Gracia Angelina

NIM : 2301857456