Heap and tries

Heap

Heap adalah pohon complete binary tree biner yang berdasarkan memenuhi properti heap. Property heaps antara lain :

• Min Heap
• Setiap node lebih kecil dari masing-masing childnya
• Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node

• Max Heap
• Setiap node lebih besar dari masing-masing childnya
• Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node

• Min-Max Heap
• Heap dengan Min heap pada level ganjil dan Max heap pada level genap

Heap dapat diimplementasi dengan array maupun dengan linked list. Aplikasi heap adalah sebagai berikut:

• Priority Queue
• Selection algorithm
• Dijkstra's Algorithm
• Prim Algorithm

Implementasi heap menggunakan array :

1. Array dimulai dengan indeks ke 1
2. Rumus umum aplikasi heap dengan array (x adalah current node):
1. Parent(x): x/2
2. Left-child(x): 2*x
3. Right-Child(x): 2*x+1
4. Min Head
3. Find-Min
4. Minimum node terletak pada root
5. Insertion pada Min-heap
6. Insert node selalu berurutan dari level paling rendah dengan urutan left ke right
7. New node selalu menjadi leaf node
8. Sesuikan sesuai heap properties secara rekursif

• Deletion-Min pada Min-Heap
• Node yang dihapus selalu root karena merupakan node paling kecil, lalu diganti dengan node yang paling terakhir di insert
• Sesuaikan dengan heap properties secara rekursif

• Max Heap
• Insertion dan deletion untuk Max heap, hanya saja disesuakan dengan properties Max-Heap

• Min-Max Heap

1. Insert node sesuai urutan, lalu cek upheap lalu sesuaikan dengan properties level.
2. Umumnya dilakukan penyesuaian rekursif dengan urutan sebagai berikut:
3. Parent
4. Grand Parent
5. Deletion selalu dilakukan pada root, lalu sesuaikan dengan downheap sesuai properties
6. Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebahai berikut:
7. Grand child
8. Child ( grand child disesuaikan dengan parentnya)

Tries

• Tries adalah tree yang dilakukan untuk menyimpan array asosiatif.
• Properties pada tries: 

- Setiap vertex/node merepresentasikan satu huruf.

- Root merepresentasikan karakter kosong.

Aplikasi pada trees adalah fitur auto-complete yang ada pada web-browser