Heap

Heap adalah complete binary tree yang berbasis struktur data dan memenuhi aturan heap. Tree pada heap and deap tidak memenuhi aturan BST yang harus terurut secara inorder, yang penting tree tersebut mengikuti aturan heap.

Jenis - jenis heap :
Min Heap : node paling kecil adalah root dan semakin kebawah levelnya semakin besar
Max Heap : node paling besar adalah root dan semakin kebawah levelnya semakin kecil
Min-Max Heap : min-heap dan max-heap levelnya saling bergantian pada tree

Min Heap

Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Lakukan upheap, yaitu compare key dengan parentya, jika node parent > key, maka swap. Jika tidak maka biarkan saja
- Lakukan point ke-2 berulang kali jika setelah diswap masih parent > key. namun stop jika key sudah berada pada posisi root.

Deletion
- Operasi delete hanya terjadi pada rootnya saja.
- Gantikan elemen yang didelete dengan node yang berada pada index terakhir
- Lakukan downheap, yaitu compare dengan salah satu childnya yang terkecil. jika node tersebut > child terkecil, maka swap
- Lakukan point ke-3 jika setelah diswap node tersebut masih memiliki anak. Namun stop jika node sudah dalam posisi leaf atau node tersebut < child terkecilnya

Max Heap

Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Lakukan uphead, yaitu compare key dengan parentnya, jika node parent < key maka swap. Jika tidak maka biarkan saja
- Lakukan point ke-2 berulang kali jika setelah diswap masih parent < key. namun stop jika key sudah berada pada posisi root.

Deletion

-Operasi delete hanya terjadi pada rootnya saja.
- Gantikan elemen yang didelete dengan node yang berada pada index terakhir
- Lakukan downheap, yaitu compare dengan salah satu childnya yang terbesar. jika node tersebut < child terbesar, maka swap
- Lakukan point ke-3 jika setelah diswap node tersebut masih memiliki anak. Namun stop jika node sudah dalam posisi leaf atau node tersebut > child terbesarnya


Min-Max Heap

Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Jika key terletak pada level min : bandingkan dengan parentnya

• Jika parent < key maka swap dan upheapmax dari parentnya (dibandingkan dengan grandparentnya dari posisi key setelah swap)
• Jika parent > key, upheapmin dari posisi key (dibandingkan dengan grandparentnya dari posisi key).

- Jika key terletak pada level max :

• Jika parent > key maka swap dan upheapmin dari parentnya (dibandingkan dengan grandparentnya dari posisi keysetelah swap)
• Jika parent < key, upheapmax dari posisi key(dibandingkan dengan grandparentnya dari posisi key).

Deletion
- Delete Min, menghapus node terkecil, yaitu root
- Delete Max, menghapus node terbesar, yaitu salah satu dari anak root
Konsep deletenya sama :
- Node yang dihapus digantikan oleh node index terakhir
- Lakukan downheapmin jika delete min, atau downheapmax jika delete max