Binary Heap: Struktur Data dengan Bentuk Complete Binary Tree

Struktur data Binary Heap adalah struktur data pohon biner (Binary Tree) yang harus memenuhi syarat dan karakteristik sebagai berikut :

• Binary Heap adalah struktur pohon biner (Binary Tree) yang berjenis Pohon Biner Lengkap (Complete Binary Tree), oleh karena itu setiap level dari suatu Binary Heap harus terisi lengkap, kecuali pada level terakhir dapat boleh tidak lengkap, tetapi pada level akhir ini cabang kiri harus terisi terlebih dahulu.
• Tinggi (height) dari suatu Binary Heap yang memiliki n simpul adalah log n.
• Pada Struktur Data Binary Heap Berjenis Binary Max Heap akan berlaku :
  • Untuk setiap simpul Y pada Binary Max Heap, jika X adalah parent dari Y, maka key atau nilai dari simpul X harus lebih besar atau sama dengan key/nilai dari simpul Y
• Pada Struktur Data Binary Heap berjenis Binary Min Heap berlaku :
  • Untuk setiap simpul Y pada Binary Min Heap, jika X adalah parent dari Y, maka key atau nilai dari simpul X harus lebih kecil atau sama dengan key/nilai dari simpul Y.

Gambar 1 menunjukkan contoh 2 jenis Binary Heap, yaitu gambar 1. a adalah contoh Binary Min Heap sedangkan pada gambar 1.b adalah contoh Binary Max Heap.

Penyisipan Simpul Baru Pada Binary Heap Tree

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

• Lakukan penelusuran Breadh First Traversal atau Level Order Traversal pada pohon Binary Heap dan sisipkan simpul baru pada urutan terakhir langkah penelusuran level order traversal tersebut.
• Bandingkanlah key/nilai simpul baru dengan parent (induk) dari simpul baru tersebut, jika key/nilai simpul baru lebih kecil dari key/nilai simpul parent (induk) maka pertukarkan simpul parent dengan simpul baru
• Ulang langkah diatas sampat syarat Min Heap yaitu setiap simpul parent harus lebih kecil atau sama dengan simpul child (anak) terpenuhi.

Gambar 2 menunjukkan langkah-langkah yang perlu dilakukan menyisipkan simpul yang memiliki nilai/key 15 kedalam suatu Binary Min Heap yang sudah ada.

Gambar 2. Contoh Penyisipan Simpul Baru Pada Binary Min Heap, Sumber : Dok. Pribadi

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

• Lakukan penelusuran Breadth First Traversal atau Level Order Traversal pada Pohon Binary Heap, dan sisipkan simpul baru pada urutan terakhir langkah penelusuran level order traversal tersebut
• Bandingkanlah key/nilai simpul baru dengan parent (induk) dari simpul baru tersebut, jika key/nilai simpul baru lebih besar dari key/nilai simpul parent (induk) maka pertukarkan simpul induk dengan simpul baru.
• Ulang langkah diatas sampai syarat Max Heap yaitu setiap simpul induk harus lebih besar atau sama dengan simpul child terpenuhi.

Penghapusan/Pengeluaran Simpul Akar (Root) Pada Binary Heap

Proses mengeluarkan simpul akar pada Binary Min Heap berarti menghapus/mengeluarkan simpul yang memiliki nilai/key terkecil pada Binary Min Heap. Langkah-langkah untuk mengeluarkan simpul akar pada Binary Min Heap adalah :

• Hapus/Keluarkan Simpul Akar
• Pindahkan simpul yang berada pada urutan terakhir penelusuran level order traversal ke simpul akar dari Binary Min Heap
• Bandingkan nilai/key simpul yang dipindahkan dari langkah diatas dengan child (anak) dari simpul tersebut, jika simpul anak dari simpul yang baru dipindahkan tersebut lebih kecil dari nilai/key simpul baru yang dipindahkan, maka pertukarkan simpul baru tersebut dengan simpul anak yang terkecil nilainya.
• Ulang langkah diatas sampai seluruh syarat Min Heap dipenuhi yaitu setiap simpul parent (induk) memiliki nilai/key yang lebih kecil atau sama dengan simpul child-nya.

Gambar 3 berikut menunjukkan proses pengeluaran simpul akar dari suatu Binary Min Heap.

Gambar 3. Contoh Penghapusan/Pengeluaran Simpul Akar Pada Binary Min Heap, Sumber : Dok. Pribadi

Proses mengeluarkan simpul akar pada Binary Max Heap berarti mengeluarkan nilai terbesar yang ada pada Binary Max Heap tersebut. Langkah-langkah untuk mengeluarkan simpul akar pada Binary Max 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 Max Heap
• Bandingkanlah nilai/key simpul yang dipindahkan pada langkah diatas dengan child dari simpul tersebut, jika nilai/key simpul anak dari simpul baru yang dipindahkan tersebut lebih besar dari key/nilai simpul yang baru dipindahkan maka pertukarkan simpul yang baru dipindahkan tersebut dengan simpul anak yang terbesar nilainya.
• Ulang langkah diatas sampai syarat Max Heap terpenuhi yaitu setiap simpul induk harus lebih besar atau sama dengan simpul child.