Data Structures – Heaps and Tries
By Emanuel Lienardi - 6:52 AM
Heap
- 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;
- Array dimulai dengan indeks ke 1
- Rumus umum aplikasi heap dengan array (x adalah current node):
- Parent(x): x/2
- Left-child(x): 2*x
- Right-Child(x): 2*x+1
Min Heap
- Find-Min
- Minimum node terletak pada root
- Insertion pada Min-heap
- Insert node selalu berurutan dari level paling rendah dengan urutan left ke right
- New node selalu menjadi leaf node
- 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
- Insert node sesuai urutan, lalu cek upheap lalu sesuaikan dengan properties level.
- Umumnya dilakukan penyesuaian rekursif dengan urutan sebagai berikut:
- Parent
- Grand Parent
- Deletion selalu dilakukan pada root, lalu sesuaikan dengan downheap sesuai properties
- Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebahai berikut:
- Grand child
- 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
0 comments