Heaps & Tries

Heap Concept =>
- Heap adalah struktur data berbasis pohon biner lengkap yang memenuhi properti heap.
- Apa jenis tumpukan properti?
  + Min Heap: setiap elemen simpul lebih kecil dari elemen anak-anaknya.
  + Max Heap: setiap elemen simpul lebih besar dari anak-anaknya.

Heap Applications =>
- Antrian Prioritas
  + Algoritma Seleksi (menemukan elemen min / maks, median, elemen kth-terbesar, dll).
  + Algoritma Dijkstra (menemukan jalur terpendek dalam grafik)
  + Algoritma Prim (menemukan pohon rentang minimum)

- Heap Sort
  + Algoritma O (n.lg (n)).

Array Implementation =>
- Tumpukan biasanya diimplementasikan dalam sebuah array.
- Elemen-elemen disimpan secara berurutan dari indeks 1 ke N dari atas ke bawah dan dari simpul        kiri ke kanan pohon.
- Root disimpan dalam indeks 1 (kami membiarkan indeks 0 kosong / tidak digunakan, untuk tujuan      kenyamanan).

Insertion in Min-Heap =>
- Kami ingin memasukkan elemen baru ke dalam heap, tetapi kita harus mempertahankan properti        heapnya.
- Masukkan elemen baru di akhir heap (setelah indeks elemen terakhir).
- Upheap elemen baru (memperbaiki properti timbunannya)

Upheap in Min-Heap =>
- Bandingkan nilai simpul saat ini (mulai dengan simpul yang disisipkan) dengan nilai induknya.          Jika nilai simpul saat ini lebih kecil dari nilai induknya daripada menukar nilainya dan teruskan          upheap simpul induknya.
- Berhenti jika nilai induknya lebih kecil dari nilai simpul saat ini atau simpul saat ini adalah root          (tidak memiliki induk).

Deletion in Min-Heap =>
- Di sini kita hanya membahas penghapusan elemen terkecil yang terletak di root.
- Ganti root dengan elemen terakhir dari heap.
- Kurangi jumlah elemen dalam tumpukan.
- Downheap root (memperbaiki properti heapnya).

Downheap in Min-Heap =>
- Bandingkan nilai node saat ini (mulai dengan root) dengan nilai anak kiri dan kanannya. Tukar            simpul saat ini dengan anak terkecil dan lanjutkan downheap pada simpul (anak) itu.
- Berhenti jika nilai simpul saat ini lebih kecil dari nilai anak-anaknya atau simpul saat ini adalah          daun (tidak memiliki anak).

Min-Max-Heap =>
- Kondisi tumpukan bergantian antara level minimum dan maksimum ke level
  + Setiap elemen pada level genap / ganjil lebih kecil dari semua anak-anaknya (level min).
  + Setiap elemen pada level ganjil / genap lebih besar dari semua anak-anaknya (level maksimal).
- Tujuan dari tumpukan minimum adalah untuk memungkinkan kami menemukan elemen tumpukan     terkecil dan terbesar sekaligus.

Tries =>
- Mencoba, (secara teknis) diucapkan "pohon" seperti dalam pengambilan, alias pohon digital,              (terkompresi) pohon radix, pohon awalan.
- Mereka adalah pohon khusus di mana simpul tidak penting.
- Sebagai gantinya, "kunci" atau "nilai" atau "payload" dikaitkan dengan tepi, dan node hanya ada        untuk kenyamanan.
- Nilai sebenarnya di pohon hanya ada di daun, dan saudara kandung berbagi apa yang disebut              awalan umum.

referensi = https://www.codingblocks.net/podcast/data-structures-heaps-and-tries/