Macam-macam heap:
1. Min Heap (ascending order)
2. Max Heap (descending order)
3. Min-Max Heap
Aturan Heap mirip dengan aturan binary tree biasa, tetapi ditambah spesifik, seperti:
Min heap: memiliki ciri root nya merupakan bilangan terkecil. Heap biasanya menggunakan implementasi array yang dimulai dari index ke 1 (root) untuk mempermudah perhitungan rumus.
Contoh ilustrasi:
Terlihat angka 7 merupakan nilai minimum dan diletakkan di root
Bentuk Array dan index dr tree disamping
7, 15, 10, 18, 28, 17, 12, 21, .....
1, 2, 3, 4, 5, 6, 7, 8, ....
Rumus untuk mencari f(x), dimana x merupakan current node:
- Parent(x) = x/2
- Anak kiri(x) = 2*x
- Anak kanan(x) = 2 *x+1
Jadi, pembuktiannya:
2. misalkan kita mau mencari anak kanan dari 15. 15 merupakan index ke 2. Maka 2*2 + 1 = 5. Jadi anak kanan dari 15 adalah index ke 5 yaitu 28.
Nilai min dari min-heap selalu berada di index pertama atau di root
Cara push heap di min-heap adalah dengan metode push-uphead. Isi dari index paling akhir. Lalu swap (tukar) dengan parent nya jika value childnya lebih kecil. Tukar terus sampai value anaknya nya lebih besar daripada parent nya atau sampai dengan root (index ke 1).
Cara delete di min-heap adalah dengan membuang root nya saja (value terkecil/index ke 1). Setelah selesai delete, maka tukar root dengan index terakhir dari heap. Lalu sesuaikan lagi nilai minimum root dengan cara tukar dengan child bagian kanan/kiri nya (downheap root) sampai nilai paling kecil kembali ke root nya.
Max Heap: memiliki ciri root nya merupakan bilangan terbesar. Heap biasanya menggunakan implementasi array yang dimulai dari index ke 1 (root) untuk mempermudah perhitungan rumus.
Cara push dan delete nya sama dengan min-heap, tapi dia fokus dari besar-kecil.
Min-Max Heap: Tiap kedalaman genap selalu berisi nilai min dari anak-anaknya. Sedangkan tiap kedalaman ganjil selalu berisi nilai max dari anak-anaknya.
Contoh ilustrasinya:
Nilai Minimum selalu berada di rootnya. Sedangkan nilai max selalu berada di salah satu anak dari root nya (baik kanan atau kiri nya) (level 1).
Insertion selalu dari index paling terakhir. Dan intinya adalah baris yang min level dibandingkan dengan baris yang min level atasnya. Sedangkan baris yang max level dibandingkan dengan max level atasnya.
Jika node baru berada di kedalaman genap (min):
Jika parent nya lebih kecil dari node barunya maka tukar dan berlakukan upheapmax
Jika parent nya lebih besar dari node barunya maka berlakukan upheapmin
Jika node baru berada di kedalaman ganjil (max):
Jika parent nya lebih besar dari node barunya maka tukar dan berlakukan upheapmin
Jika parent nya lebih kecil dari node barunya maka berlakukan upheapmax
Upheapmin
Bandingkan nilai node saat ini dengan nilai grand-parent-nya. Jika nilai node saat ini lebih kecil dari nilai induknya daripada swap nilai-nilai mereka dan teruskan sampai grand-parent node.
Upheadmax
Bandingkan nilai node saat ini dengan nilai grand-parent-nya. Jika nilai node saat ini lebih besar dari nilai induknya daripada swap nilai-nilai mereka dan teruskan sampai grand-parent node.
Delete hanya bisa dilakukan pada nilai max dan nilai min
Jika melakukan delete pada nilai minimum atau maximum, maka gantikan nilai root dengan element di index terakhir (genap/ganjil). Mirip caranya dengan min heap.
TRIES adalah tree yang tiap setiap vertex nya mempresentasikan 1 kata (string)
Ciri-ciri nya:
1. Root nya selalu berupa karakter NULL (kosong) (takde isi)
2. Setiap vertex nya mempresentasikan 1 kata (string) yang terdiri dari kumpulan char
3. Ada boolean yang menyatakan end. (Kata itu sudah berakhir)
Contoh ilustrasinya:
Contoh aplikasi Tries:
1. Spell checker
2. Autocomplete/predictive text
3. Dictionary searching
Sekian pertemuan minggu ini.
