Deap (Double ended heap) mirip dengan Min-Max Heap. Bedanya, bila min-max heap, min dan max nya selang seling atas bawah maka pada deap min di kiri dan max ada di kanan.
Contoh deap:
Jadi pada deap:
- Root nya blank(null)
- Left subtree dari root berisi min heap
- Right subtree dari root berisi max heap
Partner adalah node yang berada di posisi yang sama bila subtree min-heap dan max-heap ditumpuk menjadi 1. Contoh:
Jika partner tidak ada maka yang dianggap partner adalah partner dari node yang seharusnya menjadi partner, seperti partner node 9 merupakan 40.Partner dari 10 adalah 25, partner dari 40 merupakan 8,9 dan 30.
Untuk mencari lokasi partnernya :
•
Min-partner
-> x-x/2
•
Max-partner
-> x+x/2
•
Jika lokasi
partnernya kosong, maka partnernya menjadi parent dari posisi partner yang
seharusnya.
•
Parent min
partner -> (x-x/2)/2
•
Parent max
partner -> (x+x/2)/2
Cara insert deap:
•
Node baru
masuk di index terakhir.
•
Periksa
kondisi pada elemen partner :
- Jika insert pada min-heap
tetapi nilainya lebih besar dari max-partner maka tukar.
- Jika insert pada max-heap
tetapi nilainya lebih kecil dari min-partner maka tukar.
•
Lakukan
Min-upHeap atau Max-upHeap berdasarkan lokasi elemen baru.
Cara delete deap:
•
Ada 2 jenis :
delete min dan delete max.
•
Jika delete
min, maka yang dihapus adalah root dari min-heap. Jika 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.
Tidak ada komentar:
Posting Komentar