Heap & Tries (Data Structure)

Heap & Tries 

Heap 

Heap adalah Complete Binary Tree yang menggunakan konsep Heap.

Ada dua jenis Heap :

1. Min Heap : Dimana setiap node elemen nya akan lebih kecil daripada node anaknya (Root nya akan menjadi nilai terkecil dalam tree ).
2. Max Heap : Berbanding terbalik dengan min Heap yaitu dimana setiap node nya akan lebih besar daripada node anaknya (Root nya akan menjadi nilai terbesar dalam tree )

Ada satu jenis lagi heap yang merupakan gabungan antara min heap dan max heap yaitu ; Min-Max Heap , yang dimana dimulai dari root yang menjadi min heap dilanjutkan dengan anaknya yang sebagai max heap dan subtree berikutnya akan kembali ke Min heap begitu seterusnya.

Min - Heap

Setiap node nya akan lebih kecil dari node child nya. Dan root nya akan menjadi nilai terkecil dari tree tersebut dan nilai terbesar berada pada di salah satu leaf node tree tersebut. 

Implementasi nya biasanya menggunakan arraylist karena lebih mudah daripada Linked List.

Methode implementation of min heap :

• Find-min : Dengan mudah dapat diketahui karena root dalam min heap akan selalu menjadi value terkecil pada tree tersebut
• Insert : Seperti operation method pada tree lainnya min heap juga ada operasi untuk memasukan datanya
• Deletion : Menghapus value dalam tree dengan tetap menuruti syarat dalam min heap tree

Dalam implementasi array ;

Root tree tersebut akan menjadi index 1 pada arraynya. Kenapa bukan 0 karena untuk memudahkan mencari letak parent tersebut seperti untuk misal index 2 untuk mencari parent nya yaitu dengan membagi dengan angka (int) 2 sehingga didapatkan hasilnya 1 dan bukan 0 oleh sebab itu digunakan nya mulai index ke-1.

Pemberian index pada tree yaitu dari kiri ke kanan secara menurun.

Misalkan index berada di : x

Hubungan antara node dalam tree 

Parent (x) : x/2

Left-Child(x) : 2*x

Right-Child(x) : 2*x+1

Hubungan diatas merupakan alasan mengapa index root adalah 1 supaya dapat digunakan hubungan tersebut.

Find min in Min heap

Dalam operasi find min sangatlah mudah karena aturan dalam min heap sudah dipastikan root nya adalah nilai terkecil dalam tree tersebut

Insertion

Setiap ada elemen yang masuk , harus tetap konsisten mengikuti aturan dalam heap nya. Dan juga setiap elemen baru akan dimasukan awal nya di index paling akhir. Jika saat data baru dimasukan tidak sesuai dengan aturan min-heap maka perlu methode fixing tree yaitu uphead elemennya.

Uphead :

Membandingkan node yang dimulai dari index data yang baru dimasukan dan kembali ke node root. Value yang berada pada index data yang baru akan dibandingkan dengan parentnya, jika parent nya lebih besar daripada value yang baru tersebut maka value nya ditukar dan dilanjutkan uphead parent nodenya. Proses akan berhenti jika sudah mencapai root / tidak ada parent.

Deletion 

Pada min heap deletion hanya terjadi pada root nya atau head sehingga perlu digantikan posisinya awalnya dengan data dari index terakhir dari heap. Hal ini berlaku juga untuk Max-Heap . Setelah itu juga menghapus jumlah total data dalam heap tersebut. Kemudian dilakukan DownHeap root untuk memperbaiki kesalahan yang ada dalam heap setelah pengubahan data.

DownHeap pada root yaitu dengan membandingkan value dirinya ke child nya sampai ke leaf node terkecilnya. Jika ada value yang lebih kecil dari value root tersebut maka akan terjadi pertukaran data antara yang lebih kecil. Untuk menentukan root tersebut akan membandingkan value nya dengan yang mana maka kita ambil dari node child terkecil dari node tersebut dan kemudian membandingkan node anak dengan value terkecil dengan value node nya.

Max Heap

Tidak begitu berbeda dengan min heap hanya saja semua yang terjadi dan aturan dalam min-heap ditukarbalik seperti pada contoh untuk root pada Max heap merupakan data terbesar dalam tree tersebut dan setiap node dalam tree akan mempunyai child node yang lebih kecil daripada node tersebut. 

Untuk operasi Method nya pun hampir sama :

• Find-max Heap  : mereturn data root / pada index pertama
• Insertion : Sama seperti min heap dimana memerhatikan aturan dari max-heap yang berbanding terbalik dengan min-heap
• Deletion : Operasi menghapus data dengan menuruti aturan max-heap

Min-Max Heap

Kondisi heap nya akan bergantian antara minimum dan maksimum per level nya / height. 

Pada min-max heap root nya akan sama seperti konsep min heap dimana merupakan data terkecil dalam tree. Kemudian diikuti dengan data terbesar pada tree yaitu salah satu dari child rootnya. 

Untuk operasi Find(x) max dan min nya yaitu :

Find-Min(x) : mereturn value yang dimana terletak pasti pada root nya 

Find-Max(x) : yaitu mereturn data child dari root dan membandingkan antara child kiri ato kanan yang lebih besar.

Insertion Min-Max Heap

Seperti biasa pada heap yaitu dimana setiap data baru akan pertama kali diletakkan pada index terakhir dalam tree. Kemudian melakukan uphead untuk melakukan perbaikan dalam tree supaya sesuai dengan konsep min-max heap. Konsep nya berbeda dengan min-heap dan max-heap dan lebih kompleks.

Ada 2 kemungkinan yang akan terjadi dalam insertion min-max heap :

• Node baru berada di level min

1. Kondisi : Jika parent dari node baru lebih kecil maka tukar kedua valuenya dan lakukan upheadmax dari parentnya.
2. Else : Upheadmin dari node baru                   

• Node baru berada di level max

1. Kondisi : Jika parent dari node baru lebih besar maka tukar kedua valuenya dan lakukan upheadmin dari parentnya.
2. Else : Upheadmax dari node baru     

Upheadmin

Membandingkan value currNode nya dengan value grand parent dari currNode. Jika value dari currNode dan lebih kecil dari grand parent nya maka tuker value keduanya dan lakukan upheadmin kembali dari grand parent nodenya

Upheadmax

Membandingkan value currNode nya dengan value grand parent dari currNode. Jika value dari currNode dan lebih besar dari grand parent nya maka tuker value keduanya dan lakukan upheadmax kembali dari grand parent nodenya.

Deletion 

Deletion pada tree tersebut ada dua macam yaitu; deletion of smallest element dan deletion of largest element.

Deletion of smallest element

1. Mengganti value root dengan elemen terakhir dari heap / data pada index terakhir.
2. Mengurangi jumlah data dalam heap nya
3. Kemudian lakukan downheapmin dari root

Deletion of largest element

1. Mengganti value child dari root (bisa child kiri atau kanan tergantung dari yang mana paling besar nilainya) dengan elemen terakhir dari heap / data pada index terakhir.
2. Mengurangi jumlah data dalam heap nya
3. Kemudian lakukan downheapmax dari root

Downheapmin 

Andaikan m merupakan value terkecil pada currNode child dan grandchild. 

Jika m adalah grandchild dari currNode maka :

1. Jikalau m lebih kecil daripada currNode : Tukar value keduanya, kemudian jika m lebih besar daripada parentnya maka tukar valuenya lagi. Lanjut lakukan downheapmin dari m.

Jika m adalah child dari currNode nya maka :
Jika m lebih kecil daripada currNode maka tukar valuenya.

Downheapmax

Hampir sama dengan downheapmin tapi hubungan operasi berbanding terbalik

Aplikasi Heap : 

• Heap Sort : Salah satu methode sort yang terbaik dan tidak ada masalah no quadratic scenarios.
• Selection : Seperti pada kasus Find max(x) dan Find min (x)
• Graph : Implementasi minimal spanning tree algorithm

Tries

Prefix Tree yang terdiri dari data secara berurut yang disimpan dalam array. Tries digunakan untuk mencari kata dalam data kamus kata dengan prefix dari suatu kata. Pengaplikasian nya yaitu dalam auto-correction pada smarthphone.

Tries adalah tree dimana setiap vertex nya mewakili sebuah kata atau sebuah prefix. Root pada tries mewakili empty character. Length sebuah kata dihitung dari jarak antara root ke last edge dari sebuah kata.