Heap and Tries

Heap

Heap adalah struktur data khusus berbasis pohon di mana pohon adalah complete binary tree. Umumnya, Heaps dapat dua jenis:
Max-Heap: dalam Max-Heap, key yang ada di node root harus terbesar di antara key yang ada di semua child. Properti yang sama harus dapat direkursif untuk semua sub-tree di binary tree.


Min-Heap: dalam Min-Heap, key yang ada di node root harus minimum di antara key yang ada di semua child. Properti yang sama harus dapat direkursif  untuk semua sub-tree di binary tree.

• 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:
1. Parent
2. Grand Parent
• Deletion selalu dilakukan pada root, lalu sesuaikan dengan downheap sesuai properties
• Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebahai berikut:
1. Grand child
2. 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

Sumber : http://gabrielyakub.blogspot.com/2016/05/pertemuan-8-heap-tries-hashing.html