Min-Max Heap

Bagi yang sudah mengerti prinsip dasar heap, pasti akan merasa agak rumit untuk memahami Min-Max Heap dan Deap. Apalagi bagi yang belum mengerti prinsip dasar heap. Pasti akan merasa sangat rumit untuk memahami materi ini. Jadi, yang belum mengerti prinsip dasar heap, baca saja di sini


Min-Max Heap
Min-Max Heap adalah kombinasi dari min heap dan max heap di mana masing-masing level akan berganti-ganti antara min heap dan max heap. Heap jenis ini berguna untuk langsung menemukan nilai min dan max dalam 1 heap saja.
Ini contoh min-max heap:

Gambar ini sengaja dibuat se-user-friendly mungkin.

Jadi, selang-seling antara max dan min. Simpel kan bentuknya? Tapi insertion dan deletionnya rumit bukan main. Mau coba dilihat? Persiapkan Mental dan Pikiran Anda. Here we go!

Insertion

Saat sebuah data baru dimasukkan, proses yang akan dilakukan dipengaruhi oleh lokasi data baru tersebut.
Jika data baru berada di level min, maka bandingkan dengan parentnya. Jika parent < newnode maka swap dan upheapmax dari parentnya. Jika tidak, upheapmin dari posisi newnode.
Insertion di level max berlaku hal yang serupa, namun berbeda tanda dan berbeda jenis upheap. Selebihnya, sama.
Upheap dalam min-max heap berbeda dengan upheap biasa. Upheap dalam kasus ini membandingkan dengan grandparent; bukan dengan parent.

Berikut contoh penerapannya:

angka 1 dimasukkan sebagai newnode. Karena berada di level max, maka jika 1<10, maka swap.

1 dan 10 diswap. Kemudian, dari posisi 1, di-upheapmin. karena 1<2, maka 1 dan 2 diswap.

hasil akhirnya pun menjadi begini.







Berikut contoh insertion bila dalam level min:

newnode 85 masuk di level min. Maka, 85 dibandingkan dengan parentnya (80).







ternyata 85>80, maka swap. Kemudian, 85 di-upheapmax. Tapi, karena 85<90, maka 85 tetap di posisinya.





Sejauh ini, semoga dimengerti. Bahannya memang sulit dimengerti. Namun, berusahalah. Sedikit lagi..

Deletion

Deletion dalam min-max heap ada 2: delete min dan delete max. Jika delete min, maka root langsung dihapus. Jika delete max, maka angka max dari children root akan dihapus.

Berikut penerapannya.

1. Delete min

Wolverine datang dan mencakar node 1. 1 pun hilang entah ke mana. Untuk semua children dan grandchildren nya dia meninggalkan pesan agar yang terkecil akan menggantikan dia.

80 (node terakhir), sebagai pengacara naik menggantikan 1 untuk sementara. Dia meneruskan wasiat si "1" untuk mencari anak atau cucu terkecil dan lebih kecil dari dirinya (80).


2 pun terpilih untuk menggantikan 1. Maka, 2 swap dengan 80. 80 pun mengecek kembali bilamana ada children/grandchildren dari 2 yang paling kecil dan lebih kecil dari dirinya.

10 terpilih menggantikan 80. Dan demikianlah berakhir proses downheap dari delete min.





2. delete max
mirip dengan delete min, namun semua dimulai dari level 2. Karena malas edit di paint lagi, maka sesi ini sengaja tanpa gambar. Bayangkanlah sendiri.

saat wolverine datang dan membunuh 1, ternyata cyclops datang dan ingin membunuh anak 1 yang paling besar. 100 pun dibunuhnya. Ternyata, 100 sudah meninggalkan wasiat agar anak dan cucu nya yang terbesar naik untuk menggantikan dia.

Kembali, 80 sebagai pengacara (kebetulan saja dia node paling akhir lagi), naik menggantikan 100 untuk sementara. Dia meneruskan wasiat dari almarhum 100. Anak/cucu nya yang paling besar adalah 75. Namun, karena 80 merasa 75 lebih kecil dari dia, maka 75 tidak pantas untuk menggantikan posisinya. Maka, tidak ada swap yang terjadi.

Demikianlah akhirnya 80 menjadi pewaris tahta yang ditinggalkan 100. Anak dan cucunya dibiarkan melarat.


Sekian dongeng mengenai Min-Max Heap. Semoga dapat dimengerti dan dipahami dengan baik. Semua tokoh yang terlibat tidak ada kaitannya dengan X-Men. Jangan sampai ada salah paham yang terjadi di sini. Selamat menunggu kedatangan Episode Selanjutnya: "Deap and the deap-deap durraaayyyy!!"