Heap dan tries

Nama : Raymon Elnardi
NIM   : 2301908620

      Di Blog kali ini kita akan membahas tentang Heap. berbeda dengan AVL tree dan RB Tree, Heap bukanlah Binary Search Tree. secara umum tree di buat menggunakan array agar lebih mudah menentukan posisi childernnya.
untuk mencari parent : node / 2
untuk mencari left-child : 2 * node
untuk mencari right-child ; 2 * node + 1
misalnya untuk mencari parent :2 dan 3 merupakan childern dari 1 karena 2/2 = 1 dan 3/2 = 1 (karena integer).

inilah mengapa biasanya root pada heap berada di index 1 bukan di index 0


Heap secara umum terbagi menjadi 3 : Min Heap, Max Heap, dan Min-Max Heap.

secara umum, heap memiliki 3 buah fungsi
1. Find min atau max ( tergantung jenis heap)
2. Insert (memasukkan node baru ke leaf)
3. pop (menghapus node yang berada di root)

- Min Heap adalah Binary Tree yang setiap elemnt dari node-nya bernilai lebih kecil dibandingkan element dari childern-nya
- Ini berarti elemenet terkecil berada di root dari tree
- element tebesarnya berada disalah satu node leaf

- Max Heap adalah Binary Tree yang setiap elemnt dari node-nya bernilai lebih besar dibandingkan element dari childern-nya
- Ini berarti elemenet terbesar berada di root dari tree
- element tekecilnya berada disalah satu node leaf

- Min-Max Heap adalah heap gabungan dari Min heap dan Max heap
- pada level genap semuanya Min heap, dan pada level ganjil semuanya Max heap
- rootnya adalah nilai terkecil (root berada di level 0)