Struktur Data Binary Min-Max Heap dan Binary Max-Min Heap

Struktur data Binary Min-Max Heap dan Binary Max - Min Heap adalah struktur data Binary Heap yang menggunakan dan menggabungkan karakteristik 2 jenis Binary Heap yaitu karakteristik Min Heap dan karakteristik Max Heap. Pada struktur data Binary Min - Max Heap dan Binary Max - Min Heap berlaku syarat dan karakteristik sebagai berikut :

• Binary Min-Max Heap dan Binary Max-Min Heap adalah struktur pohon biner (Binary Tree) yang berjenis Complete Binary Tree oleh karena itu setiap level dari suatu Binary Min-Max Heap dan Binary Max - Min Heap harus terisi lengkap, kecuali pada level terakhir dapat boleh tidak lengkap tetapi pada level akhir ini simpul harus terisi berurutan mulai dari kiri ke kanan.
• Tinggi (Height) dari suatu  Max-Min Binary Heap dan Min-Max Binary Heap yang memiliki n simpul adalah ⌊log ₂ n⌋
• Pada Struktur Data Binary Heap berjenis Min-Max Heap dan Max-Min Heap akan berlaku :
  • Untuk setiap simpul X yang berada dan diletakkan pada level Min, maka seluruh turunan simpul X (descendant node dari X) tersebut  harus memiliki nilai lebih besar dari simpul X tersebut, syarat ini tidak berlaku bila Simpul X adalah simpul daun.
  • Untuk setiap simpul Y yang berada dan diletakkan pada level Max, maka seluruh turunan simpul Y (descendant node dari Y) tersebut harus memiliki nilai lebih kecil dari simpul Y tersebut, syarat ini tidak berlaku bila Simpul Y adalah simpul daun.
  • Untuk setiap simpul X yang berada pada level Min dan memiliki ancestor yang berada pada level Min maka simpul ancestor tersebut harus memiliki nilai lebih kecil dari simpul X, syarat ini tidak berlaku bila Simpul X tidak memiliki ancestor yang berada pada level Min, dan atau Simpul X adalah simpul akar.
  • Untuk setiap simpul X berada pada level Max dan memiliki ancestor yang berada pada level Max, maka simpul ancestor tersebut harus memiliki nilai lebih besar dari simpul Y, syarat ini tidak berlaku bila simpul Y tidak memiliki ancestor yang berada pada level Max, dan atau Simpul Y adalah simpul akar.

Contoh dari suatu Struktur Data Binary Min-Max Heap dapat dilihat Gambar 1.a, sedangkan contoh Struktur Data Binary Max-Min Heap dapat dilihat pada Gambar 1.b. 

Dari gambar 1 dapat dilihat bahwa pada struktur data Min-Max Heap dan Max-Min Heap, maka level Min dan level Max akan diletakkan secara berselang-seling. Pada Binary Min - Max Heap maka level 0 atau level simpul akar akan menerapkan karakteristik Min Heap (Level 0 akan bertipe Level Min), sedangkan pada Binary Max-Min Heap, maka level 0 atau level simpul akar akan menerapkan karakteristik Max Heap (Level 0 akan bertipe Level Max). Untuk mempersingkat pembahasan maka pada artikel ini hanya akan dicontohkan penyisipan dan penghapusan simpul dari Struktur Data Binary Min - Max Heap.

Penyisipan Simpul Baru pada Binary Min - Max Heap Tree

Untuk menyisipkan simpul baru pada Binary Heap Tree berjenis Min - Max Heap maka langkah - langkah yang dapat dilakukan adalah :

• Lakukanlah penelusuran Breadth First Traversal atau Level Order Traversal pada Binary Heap dan sisipkan simpul baru pada urutan terakhir langkah penelusuran Level Order Traversal tersebut.
• Bandingkanlah key / nilai simpul baru dengan parent dan ancestor dari simpul baru tersebut, jika posisi simpul baru tidak memenuhi karakteristik Min - Max Heap, maka perbaikilah struktur Min-Max Heap tersebut dengan cara mempertukarkan simpul baru tersebut dengan parent atau ancestor sampai Binary Heap yang terbentuk memenuhi karakteristik Min - Max Heap.
• Ulang langkah diatas sampai syarat dan karakteristik Min-Max Heap terpenuhi.

Gambar 2  menunjukkan penyisipan suatu simpul pada Binary Min - Max Heap.

Gambar 2. Contoh Penyisipan Simpul Pada Binary Min-Max Heap. Sumber : Dok. Pribadi

Penghapusan Simpul Akar Pada Binary Min-Max Heap  

Langkah - langkah untuk menghapus simpul akar pada Min-Max Binary Heap adalah sebagai berikut :

• Hapus / Keluarkan Simpul Akar
• Pindahkan Simpul yang berada pada urutan terakhir berdasarkan penelusuran level order traversal ke simpul akar dari Binary Min-Max Heap.
• Bandingkanlah nilai / key simpul yang dipindahkan pada langkah 2 dengan child dan descendant dari simpul tersebut, lakukan pertukaran jika masih belum memenuhi syarat Binary Min-Max Heap.
• Ulang langkah 3 sampai syarat Binary Min-Max Heap terpenuhi.  

Gambar 3 menunjukkan proses penghapusan simpul akar pada suatu Binary Min-Max Heap.

Gambar 3. Contoh Penghapusan Simpul Akar Pada Binary  Min-Max Heap.Sumber : Dok Pribadi