Deap

Deap seakan-akan mirip dengan heap. Namun, pada kenyataannya, Deap lebih mirip dengan Min-Max Heap. Deap adalah Min-Max heap yang lebih sederhana. Bila min-max heap, min dan max nya selang-seling atas-bawah, maka dalam deap, min dan max nya ada di kiri dan di kanan.

Beberapa aturan utama mengenai Deap adalah:
1. root selalu NULL
2. left subtree dari root adalah min-heap
3. right subtree dari root adalah max-heap
4. hanya itu saja

sesuatu yang unik dari deap adalah sesuatu yang bernama "partner". Partner adalah pasangan dari sebuah node dari deap.  Di bawah akan dijelaskan dengan lebih detail mengenai partner.

Berikut adalah contoh dari Deap:

di sini jelas kan? di sebelah kiri itu min-heap, yang di kanan itu max-heap.








Partner
Partner adalah node yang berada di posisi yang sama bila subtree min-heap dan max-heap ditumpuk menjadi 1. misalkan, node 1 partnernya 50, node 9 partnernya 12, dst.
rumus untuk mencari lokasi partnernya adalah:

min-partner = x-2^((log x) -1)
max-partner = x+2^((log x)-1)

bila lokasi partner ternyata kosong, maka partnernya menjadi parent dari posisi partner yang seharusnya.
Supaya tidak ada di awang-awang, berikut contoh penggunaannya. Kita langsung masuk ke insertion.

INSERTION

Saat sebuah data baru dimasukkan, maka akan langsung dicek dengan partnernya. Bila posisinya tertukar, maka swap, kemudian di-upheap. Jika tidak, maka langsung saja di-upheap.

berikut contohnya:

Node 17 masuk. posisinya berada di dalam min heap. Maka, nodenya langsung dicek dengan partnernya. Partner 17 harusnya berada di index ke:
16+((log 16)-1) = 24.
Tapi, karena index 24 masih kosong, maka partner 17 adalah parent dari index 24, yaitu 15.



Karena 17>15, maka swap. Kemudian, 17 di-upheap. Karena 17<40, maka tidak ada swap yang terjadi.








Lebih simpel kan, daripada min-max heap? Berikutnya mengenai deletion.

DELETION

Deletion dalam deap ada 2: delete min dan delete max. Jika delete min, maka yang dihapus adalah root dari min-heap. Bila delete max, maka yang dihapus adalah root dari max-heap.
Setelah dihapus, seperti biasa, elemen terakhir dari heap menggantikan posisi dari yang terhapus, kemudian di-downheap. Bedanya dengan heap biasa adalah setelah di-downheap, maka akan dilakukan pengecekan terhadap partner.

Berikut contohnya:
1. delete max
bosen aja delete min yang duluan. Jadi, yang kali ini max yang duluan.

saat 50 dihapus, maka 15 menggantikan posisi 50.

kemudian, 15 di-downheap biasa.

setelah di-downheap, 15 dicek dengan partnernya: 10. Bila 15<10, maka swap. Ternyata tidak. Jadi, selesai sudah proses deletion.







2. delete min
berhubung malas untuk menggambar lagi, dan sejujurnya, delete min konsepnya sama dengan delete max, maka saya hanya bisa berkata bahwa delete min dengan delete max hanya berbeda tanda saja. Tidak lebih, tidak kurang.



Jadi, sepertinya Deap hanya segini. Jauh lebih mudah daripada Max-Min Heap, kan? Jadi, kalo uda mengerti min-max heap, pasti lebih mudah untuk memahami Deap.
Sekian dulu pembahasannya sekarang. Bisa ditunggu Episode selanjutnya: "Stack and Queue"