Double-Ended Heap (DEAP)

DEAP : double-ended heap. Merupakan tipe struktur data heap, yang mempunyai fungsi yang lebih efisien untuk mencari ataupun menghapus nilai maksimum dan minimum dari kumpulan data yang ada.

DEAP memliki karakteristik s.b.b. :

• Root tidak memiliki elemen
• Left Subtree merupakan minimum heap
• Right Subtree merupakan maksimum heap
• Jika subtree kanan tidak kosong maka, i adalah node pada subtree kiri. j adalah node yang berkoresponden pada subtree kanan. Jika j tidak ada maka node yang menjadi j adalah node pada subtree kanan yang berkoresponden dengan parent dari i. Isi data (key) dari node I harus lebih kecil atau sama dengan isi data pada node j (key)

Contoh Deap :

Operasi-operasi yang dapat dilakukan pada DEAP :

• Find-Min  : Mencari elemen terkecil dalam Deap
• Find-Max  : Mencari elemen terbesar dalam Deap
• Insert  : Memasukkan elemen baru ke dalam Deap
• Delete-Min  : Menghapus elemen terkecil dalam Deap
• Delete-Max  : Menghapus elemen terbesar dalam Deap

Node Koresponden

Tiap node pada subtree kiri mempunyai node koresponden dengan node pada subtree kanan (berada pada lokasi yang mirip). Jika tidak ada node pada lokasi partnernya, maka akan berkorespondensi dengan parent dari partnernya.

Rumus menentukan node koresponden:

•  Pada min-heap : j=i-2^[log₂^i]-1
•      Pada max-heap: j=i+2^[log₂^i]-1

Contoh :

Find-Min/Max

• untuk Find-Min , cukup panggil root dari min-heap(sub-tree sebelah kiri)
• untuk Find-Max . cukup panggil root dari max-heap(sub-tree sebelah kanan)

Insertion

• Masukkan nilai yang baru pada node selanjutnya setelah node yang terakhir . Misal : terakhir memasukkan nilai pada node dengan index-13 maka nilai yang baru tersebut dimasukkan pada node dengan index-14 .
• Cek dengan korespoden min-partner atau max partner
• Jika terletak pada min-heap , tetapi nilainya lebih besar dari max-partner maka tukar nilai mereka
• Jika terletak pada max-heap, tetapi nilainya lebih besar kecil dari min-partner maka tukar nilai mereka
• Lakukan min-upheap atau max-upheap sesuai dengan posisi barunya
• Min-upheap, yaitu upheap pada min-heap subtree
• Max-upheap, yaitu melakukan upheap pada max-heap subtree

Contoh:

Insert 50

Max Upheap

Deap setelah insert selesai

Deletion

• Simpan nilai pada node index paling akhir dalam variabel t dan nilai index dikurang 1
• Hapus root pada min-heap jika delete-min atau root pada max-heap jika delete-max
• Jika delete-min maka posisi root sekarang yang kosong diisi oleh child dengan nilai yang paling kecil , diteruskan sampai pada leaf . jika delete-max posisi root yang sekarang kosong diisi oleh child dengan nilai yang paling besar dan diteruskan sampai pada leaf
• Masukkan nilai pada variabel t tadi kedalam leaf yang kosong
• Bandingkan nilai pada variabel t dengan node-partnernya.
• Pada delete-min, jika t<max-partner maka nilainya tidak perlu ditukar tapi jika t>max-partner maka tukar kedua nilai tersebut
• Pada delete-max , jika t<min-partner maka tukar nilai nya tapi jika j>min-partner maka nilainya tidak perlu ditukar

Contoh:

Delete min

Setelah Delete Min