Heap and Tries

Nama : Dea Claresta
Nim : 2301863736

Heap

Heap adalah spesial tree, yaitu complete binary tree. Heap ada 2 tipe, max heap, dan min heap.
Min heap->node parentnya lebih kecil dr anaknya. Max heap->parentnya lebih besar dari anaknya.

Min heap-> angka paling kecil ada di root. angka paling besarnya ada di salah satu leaf. heap bisa menggunakan linked list, tp paling mudah pakai array, dimana arraynya dimulai dari 1, array ke 0 tidak dipakai agar lebih mudah.

Hubungan antar parent dengan anak kanan dan kiri dalam array sangat mudah untuk di cari, dengan x adalah array dari node itu sendiri

•Parent(x)  = x / 2

•Left-child(x)  = 2 * x

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

misalnya, node 15, x= 2, parentnya 1, anak kirinya 4, dan anak kanannya 5.

Aplikasi heap yaitu dalam Priority Queue

1. Selection Algorithms (finding min/max element, median, kth-largest element, etc).
2. Dijkstra’s Algorithm (finding shortest path in graph)
3. Prim Algorithm (finding minimum spanning tree)

Insert heap

Insert element di node array terakhir, lalu di upheap(fixing heap property).

Upheap

Dibandingkannya angka yang di insert dengan parentnya, klo yg di insert < , maka dituker, begitu terus sampai parentnya yang < dari anaknya atau angka yg diinsert sudah sampai root(ga  pnya parent).

Deletion in Min-heap

Delete hanya bisa dilakukan di angka terkecil(root), lalu root digantikan oleh element array terakhir, lalu mengurangi number element dalam heap, dilakukan downheap(fixing heap property)

Downheap

mengcompare current node(awalnya root dulu) dengan anak kanan dan kiri, lalu swap current node dengan anak paling kecilnya, lalu lanjut downheap yang anaknya. stop downheap saat parentnya > dari kedua anaknya atau sudah sampai di leaf(tidak punya child).

pics from: https://www.slideshare.net/HoangNguyen446/heaps-61679009

Max-heap 

Max-heap bisa untuk Priority Queue (yang lebih besar duluan)

Setiap node > dari anak-anaknya. Node paling besar ada di root. Prinsip Max-heap=Min-heap

Min-Max heap

Gabungan min dan max heap. Agar bisa menemukan angka terkecil dan terbesar bersamaan.

Angka terkecil ada di root, angka terbesar ada di anak kanan/kiri root. Root bisa menjadi angka terbesar kalau nodenya cuma 1(root doang)

Insertion dalam Min-max heap

insert element baru di array paling terakhir, lalu melakukan Upheap .

Upheap

1.    Jika new node ada dalam min-level :

               - If new node's parent<, maka swap ,lalu upheapmax dari parentnya

               - else, upheapmin dari new node

2.    Jika new node di max-level :

               - If newnode's parent>, maka swap, dan upheapmin dari parent

               - else, upheapmax dari new node

Upheapmin

membandingkan current node dengan grand-parentnya. jika current node< parent, maka swap, dan lanjut upheapmin grand-parent node.

Upheapmax

membandingkan current node dengan grand-parentnya. jika current node>parent, maka swap, dan lanjut upheapmax grand-parent node.

Deletion in Min-Max heap

1. Deletion smallest element

           - replace root dengan element terakhir.

           - kurangi jumlah element heap

           - downheapmin dari root

2. Deletion largest element

           - replace angka paling besar dengan last element heap

           - kurangi jumlah element heap

           - downheapmax dari node

Downheapmin 

bikin current node jd angka paling kecil dari smua node

- klo m itu grandchildren dari current node. klo grandchildrennya < current node, swap, lalu jika          m>parent, swap, trs downheapmin dari m

- klo m itu anak dari current node, dan m<current node, swap

konsep downheapmax=downheapmin

Tries

Tries (prefix tree) adalah ordered tree data structure yang digunakan untuk array associative(biasanya string). Tries mampu mencari kata dalam dictionary hanya dengan prefix dari katanya sendiri.

Tries adalah tree yang setiap vertex menghasilkan 1 kata/prefix. Root dalam tries isinya empty character. Vertex yang  jarak dari rootnya k edges , memiliki prefix dengan panjang k.