Linked List (II): Heaps & Tries

A. Heaps

Heap adalah complete binary tree yang mengikuti kaidah heap

ada 2 kaidah heap :
1. Min heap = setiap elemen node lebih kecil dari childernnya
2. Max heap = setiap elemen node lebih besar dari childernnya

1. Min Heap
- Setiap elemen node lebih kecil dari childrennya
- root adalah elemen terkecil
- heap bisa diwujudkan dengan linked list, tapi lebih mudah bila dilakukan menggunakan array

Aplikasi Heap

1. Priority Queue
- Selection Algorithms
- Dijkstra's Algorithms
- Prim Algorithm

2. Heap Sort

Implementasi Array

root adalah index ke 1

Dalam heap, kita menggunakan array dari index pertama untuk memudahkan pengerjaan

Cara menentukan elemen, misalkan suatu elemen adalah x
- parent = x / 2, cth : 15/2 = 7.5, karena integer, sehingga menjadi 7
- left-child = 2 * x
- right-child = 2 * x +1

Min - Heap Insertion
1. lakukan insert pada index terakhir
2. kita benarkan kaidah heap
kita bandigkan elemen baru dengan value diatas nya, bila lebih kecil, di swap, lakukan hingga value parent lebih besar dari elemen itu

- insert node 20

- insert node 5

Min - Heap Deletion
- dalam hal ini, hanya bisa lakukan deletion pada node nilai terkecil, yaitu root
- tukar root dengan last elemen / index terakhir
- kurangi jumlah elemen heap
- cek dan benarkan kaidah heap
1. Compare dengan left dan right child, tukar dengan value child yang paling kecil
2. stop bila node lebih kecil valuenya dari pada kedua childernnya

-Delete min, node 7, replace dengan node 28

2. Max Heap
- Semua prinsip merupakan kebalikan dari Min Heap
- root adalah node nilai terbesar

3. Min - Max Heap
- Elemen terkecil ada di root
- elemen terbesar terletak pada left / right root

- level ganjil berisi elemen - elemen yang bernilai kecil (min-level)
- level genap berisi elemen - elemen yang besar nilainya (max-level)

Min - Max Heap Insertion
- Insert dilakukan di index paling akhir
- lakukan fixing dan pengecekan pada heap

Kaidah fixing :
1. Jika kita menginsert node pada min-level
- jika node parent lebih kecil, tukar valuenya
- jika tidak, lakukan pengecekan pada grand-parentnya, kalau grandparentnya lebih besar, tukar
,lakukan sampai syarat tidak berlaku

2. Jika kita menginsert node pada max-level
- Jika node parent lebih besar, tukar valuenya
- Jika tidak, bandingkan dengan grand - parentnya, kalau grandparent lebih kecil, tukar, lakukan sampai syarat tidak berlaku

- insert 50

- insert 5

Min - Max Heap Deletion
1. Deletion elemen terkecil
- tukar root dengan elemen terakhir, kurangi jumlah elemen pada heap
- lakukan down-checking pada root

2. Deletion elemen terbesar
- tukar left / right root, yang merupakan elemen terbesar, lalu tukar dengan elemen akhir root
- lakukan pengecekan kebawah dari node

-Delete Max