Data Structure 8

Heaps

Min Heaps

Gw belajar kalo heaps itu juga adalah salah satu jenis tree yang punya aturannya sendiri. Dalam min heaps, aturannya adalah ortunya harus punya nilai yang lebih kecil dari anaknya. Biar lebih kebayang yang gw maksud, gw langsung pake gambar aja ya



Nah ini yang dimaksud dengan ortunya slalu lebih kecil dari anak-anaknya. Jadi pas insert, rootnya masuk, kalo pada insert kedua anaknya lebih kecil dari ortunya, anak dan ortu akan diswap supaya memenuhi aturan dari min heap.

Kalo deletion, misalnya kita delete angka 1. Data terakhir yang di input akan menggantikan si satu ini, misalnya yang terakhir kali kita input itu angka 100. Maka 100 bakalan jadi rootnya. Tapi kan 100 ga lebih kecil dari anak-anaknya. Nah makanya setelah kita ganti akarnya jadi 100, kita harus bandingin ulang satu per satu. pertama kita bandingin 100, 2, dan 3. Karena 100 lebih besar dari keduanya maka 100 harus diswap, dan yang akan naik ke atas adalah nilai yang lebih kecil yaitu 2. Terus kita bandingin 100, 17, dan 19. 17 akan naik dan 100 akan turun. Bandingin 100 dan 25. 25 naik, 100 turun. Selesai deh deletionnya.

Max Heaps

Max heaps itu adalah kebalikan dari min heaps. Kalo dalam min heaps ortunya lebih kecil dari anak, dalam max heaps, ortunya harus lebih gede dari anaknya.



Nah kayak kita liat gambar di atas, ortunya selalu lebih gede dari anaknya. Kalo insertion ya sama aja kayak min heap cuman kebalikannya jadi data pertama masuk. Kalo data selanjutnya lebih besar dari ortunya, bakalan diswap.

Deletionnya juga kebalikan dari min heap. Jadi kalo kita apus 100, data terakhir yang di input bakal gantiin posisi 100, misalnya 7. 7 bakal naik ke yang paling atas. Terus bakal bandingin dengan anak-anaknya. Karena 7 lebih kecil dari 19 dan 36, maka bakal diswap, tapi yang naik itu nilai yang paling besar. Dalam perbandingan 7, 19, dan 36 yang paling besar adalah 36, maka 7 kita swap dengan 36. Selanjutnya kita bandingin 7, 25. dan 1. Karena 7 lebih kecil dari 25 tapi ga lebih gede dari 1, maka kita akan swap 25 dengan 7. Deletion selesai.