Heaps & Tries

Heaps

Heap adalah sebuah data struktur berdasarkan Tree yang special di mana treenya adalah complete binary tree. Heap bisa diimplementasikan menggunakan linked list, tetapi akan lebih mudah apabila mengimplementasikannya menggunakan array. Heap adalah sebuah implementasi yang efisien dari data struktur priority queue. Jenis-jenis heap:

1. Min-Heap, setiap element node harus lebih kecil daripada element childrennya. Ini artinya nilai yang terkecil berada di root tree. Nilai terbesar berada di salah satu node leaf.

Element biasanya disimpan secara berurutan dari index 1 ke index N mulai dari node atas ke node bawah dan node kiri ke node kanan dari tree. Index 0 kita kosongkan.

Misalkan index dari current node adalah x.

• Parent(x) = x / 2
• Left-child(x) = 2 * x
• Right-child(x) = (2 * x) + 1

Inilah alasan mengapa kita menggunakan index 1 sebagai root, kalau tidak maka tida bisa mendapatkan relasi yang sesimpel ini

Insertion pada Min-Heap

Misalkan kita ingin insert sebuah element baru, pertama kita masukkan element baru pada node setelah index dari element terakhir, Kemudian akan dilakukan proses upheap di mana kita menaikkan element yang sudah kita insert ke atas dengan syarat apakah element tersebut lebih kecil dari element parentnya. Jika elementnya lebih kecil dari element parentnya, maka akan bertukar posisi dan lanjutkan lagi sampai jika element dari parentnya lebih kecil maka proses upheap berhenti.

Contoh insert(5)

Deletion pada Min-Heap

Dalam deletion, hal yang perlu kita perhatikan adalah deletion pada element terkecil yang terletak pada root. Pertama, kita delete terlebih dahulu element yang ada di root. Kemudian, kita masukkan element dari node terakhir ke root. Lalu kita lakukan proses downheap di mana kita menurunkan element yang ada di root apabila element tersebut memiliki nilai yang lebih besar dibandingkan dengan left dan right childnya. Jika tidak ada child yang nilainya lebih kecil, maka proses downheap berhenti.

Contoh deletion(7)

2. Max-Heap, setiap element node harus lebih besar daripada element childrennya. Ini artinya nilai yang terbesar berada di root tree. Nilai terkecil berada di salah satu node leaf. Prinsip insertion dan deletion dari Max-Heap sama seperti Min-Heap. Max-Heap bisa digunakan untuk membuat priority queue untuk mencari element terbesar.

3. Min-Max Heap, kondisi heap bertukar-tukaran antara minimum dan maximum dari level ke level

• Setiap element pada level genap/ganjil lebih kecil daripada semua childrennya (min-level)
• Setiap element pada level ganjil/genap lebih besar daripada semua childrennya (max-level)

Tujuan dari Min-Max Heap adalah membiarkan kita mencari element terkecil dan terbesar dari sebuah heap dalam waktu yang bersamaan.

Insertion pada Min-Max Heap

Masukkan element baru pada index setelah element terakhir. Kemudian upheap element terbarunya. Proses upheap pada Min-Max Heap sedikit berbeda dengan Min-Heap atau Max-Heap.

Jika node baru berada di min-level

• Jika parent dari node baru lebih kecil maka tukar nilai mereka dan upheapmax dari parentnya
• Else upheapmin dari node baru

Jika node baru berada di max-level

• Jika parent dari node baru lebih besar maka tukar nilai mereka dan upheapmin dari parentnya.
• Else upheapmax dari node baru

Upheapmin

Membandingkan nilai node current dengan nilai grand-parentnya. Jika nilai current node lebih kecil dari parentnya maka tukar nilai mereka dan lanjutkan upheapmin node grandparentnya.

Upheapmax

Membandingkan nilai node current dengan nilai grand-parentnya. Jika nilai current node lebih besar dari parentnya maka tukar nilai mereka dan lanjutkan upheapmax node grandparentnya.

Contoh insertion(50)

Upheapmin: 50 lebih besar dari parentnya, maka lakukan upheapmax

Upheapmax: 50 lebih besar dari grand-parentnya, maka tukarkan nilai mereka

Upheapmax: Karena node 50 tidak memiliki grand-parent, maka prosesnya selesai.

Deletion pada Min-Max Heap

Deletion element terkecil

• Gantikan root dengan element terakhir pada heap
• Downheapmin dari root

Deletion element terbesar

• Gantikan antara left atau right child dari root (tergantung mana yang lebih besar) dengan element terakhir pada heap
• Downheapmax dari node

Downheapmin

• Misalkan m adalah elemen terkecil dari children dan grandchildren (kalau ada) node current.
• Jika m adalah grandchildren dari node current maka
• Jika m lebih kecil dari node current maka
• Tukar nilai mereka
• Jika m lebih besar dari parentnya maka tukar nilai mereka
• Lanjut downheapmin dari m
• Jika m adalah children dari node current maka
• Jika m lebih kecil dari node current maka
• Tukar nilai mereka

Downheapmax sama kecuali operator relasionalnya dibalik.

Contoh deletion max

Ganti nilai max dengan node terakhir (14)

Downheapmax: cari nilai terbesar dari children dan grandchildrennya. Kemudian, tukar nilai mereka.

 Downheapmax: Karena parent 14 lebih besar dari 14, tukar nilai mereka dan lanjutkan downheapamax.

Karena 28 tidak memiliki children atau grandchildren, prosesnya selesai.

Tries

Tries adalah sebuah tree di mana setiap vertex merepresentasikan sebuah kata atau prefix. Root merepresentasikan sebuah karakter kosong(''). Sebuah vertex adalah jarak dari k edges dari root memiliki prefix assosiatif dengan panjang k.

Contoh dari Tries yang mengandung kata:

1. ALGO
2. API
3. BOM
4. BOS
5. BOSAN
6. BOR