☻Binary Heap
Binary dapat berwujud Min Heap dan Max Heap. Apa perbedaan Min Heap dan Max Heap ?
• Min Heap = Binary Heap dimana Parent Node memiliki value lebih kecil dibandingkan kedua Child Node.
• Max Heap = Max Heap adalah kebalikan dari Min Heap yaitu Parent Node memiliki value lebih besar dibandingkan kedua Child Node.
Property dari Binary Heap :
Semua element dari binary heap dapat disimpan didalam sebuah array. Elemen i dari suatu array akan mempunyai left child di 2i sedangkan right child di 2i+1. Sedangkan elemen i akan mempunyai parent di index i/2 dengan pembulatan ke bawah.
Property lain yang harus di ingat adalah semua level kecuali level terakhir harus penuh. Tinggi dari binary heap adalah log n.
Operations dari Binary Heap :
Operasi di dalam Binary Heap terdapat Searching, Insert, dan Delete.
1. Searching : Proses Searching akan sama dengan proses searching di Binary Search Tree.
2. Insertion = Proses insert selalu dilakukan dari leaf node. Kita tidak perlu melakukan komparasi dari Root Node. Kita selalu meletakkan new node di posisi leaf node paling kiri. Kita harus mengisi dari new node dari kiri ke kanan.
Sesudah new node di insert kita baru melakukan komparasi dengan parent node. Kita ambil contoh implementasi Max Heap. Jika new node memiliki nilai yang lebih besar dari parent dari new node maka kita perlu melakukan proses swap karena pada Max Heap nilai dari parent haruslah lebih besar dari child node. Proses komparasi ini harus kita lakukan sampai kita berada di root node atau kondisi sudah memenuhi syarat Min Heap atau Max Heap.
3. Deletion = Proses delete pada Binary Heap hanya dapat menghapus root node. Sesudah root node dihapus maka root node akan digantikan dengan last element atau node terakhir yang diinsert. Sesudah hal ini dilakukan kita akan melakukan komparasi. Kita ambil contoh kembali implementasi Max Heap. Jika kita menggunakan Max Heap maka kita perlu melakukan komparasi root node dengan child node yang memiliki nilai paling besar, jika ternyata nilai dari child node lebih besar maka kita lakukan swap. Hal ini harus kita lakukan sampai Binary Heap memenuhi syarat Max Heap atau Min Heap.
Implementasi dari Binary Heap :
1. Sorting Array
Kita dapat melakukan heap sort dengan mengimplementasikan binary heap. Pada saat kita menghapus root dari binary heap dan meletakkannya di akhir array kita dan melakukan proses ini sampai tidak ada node didalam Binary Heap maka kita akan mendapatkan array yang tersorting. Max Heap akan menghasilkan sorting yang ascending sedangkan Min Heap akan menghasilkan sorting yang descending
2. Priority Queue
Priority Queue akan lebih efektif jika kita menggunakan Binary Heap karena proses operasi enqueue dan dequeue dapat berjalan di O (log n).
Contoh Case pada Max Heap:
Binary dapat berwujud Min Heap dan Max Heap. Apa perbedaan Min Heap dan Max Heap ?
• Min Heap = Binary Heap dimana Parent Node memiliki value lebih kecil dibandingkan kedua Child Node.
• Max Heap = Max Heap adalah kebalikan dari Min Heap yaitu Parent Node memiliki value lebih besar dibandingkan kedua Child Node.
Property dari Binary Heap :
Semua element dari binary heap dapat disimpan didalam sebuah array. Elemen i dari suatu array akan mempunyai left child di 2i sedangkan right child di 2i+1. Sedangkan elemen i akan mempunyai parent di index i/2 dengan pembulatan ke bawah.
Property lain yang harus di ingat adalah semua level kecuali level terakhir harus penuh. Tinggi dari binary heap adalah log n.
Operations dari Binary Heap :
Operasi di dalam Binary Heap terdapat Searching, Insert, dan Delete.
1. Searching : Proses Searching akan sama dengan proses searching di Binary Search Tree.
2. Insertion = Proses insert selalu dilakukan dari leaf node. Kita tidak perlu melakukan komparasi dari Root Node. Kita selalu meletakkan new node di posisi leaf node paling kiri. Kita harus mengisi dari new node dari kiri ke kanan.
Sesudah new node di insert kita baru melakukan komparasi dengan parent node. Kita ambil contoh implementasi Max Heap. Jika new node memiliki nilai yang lebih besar dari parent dari new node maka kita perlu melakukan proses swap karena pada Max Heap nilai dari parent haruslah lebih besar dari child node. Proses komparasi ini harus kita lakukan sampai kita berada di root node atau kondisi sudah memenuhi syarat Min Heap atau Max Heap.
3. Deletion = Proses delete pada Binary Heap hanya dapat menghapus root node. Sesudah root node dihapus maka root node akan digantikan dengan last element atau node terakhir yang diinsert. Sesudah hal ini dilakukan kita akan melakukan komparasi. Kita ambil contoh kembali implementasi Max Heap. Jika kita menggunakan Max Heap maka kita perlu melakukan komparasi root node dengan child node yang memiliki nilai paling besar, jika ternyata nilai dari child node lebih besar maka kita lakukan swap. Hal ini harus kita lakukan sampai Binary Heap memenuhi syarat Max Heap atau Min Heap.
Implementasi dari Binary Heap :
1. Sorting Array
Kita dapat melakukan heap sort dengan mengimplementasikan binary heap. Pada saat kita menghapus root dari binary heap dan meletakkannya di akhir array kita dan melakukan proses ini sampai tidak ada node didalam Binary Heap maka kita akan mendapatkan array yang tersorting. Max Heap akan menghasilkan sorting yang ascending sedangkan Min Heap akan menghasilkan sorting yang descending
2. Priority Queue
Priority Queue akan lebih efektif jika kita menggunakan Binary Heap karena proses operasi enqueue dan dequeue dapat berjalan di O (log n).
Contoh Case pada Max Heap:
Comments
Post a Comment