HEAP

HEAP

    Di dalam bidang Teknik Informatika terdapat banyak sekali jenis-jenis algoritma pengurutan yang dapat digunakan untuk memecahkan masalah pengurutan. Oleh karena itu, teknik untuk memilih algoritma pengurutan yang tepat, sesuai dengan kebutuhan, dan mangkus sangat diperlukan karena masing-masing algoritma pengurutan memiliki karakteristik yang berbedabeda. Heap sort merupakan salah satu contoh algoritma pengurutan yang memiliki kompleksitas waktu asimptotik terbaik serta menerapkan teknik yang unik/khas di dalam memecahkan masalah pengurutan, yaitu dengan menggunakan heap tree. 

Pengertian Heap Tree:

    Secara umum pengertian dari heap adalah bagian dari memori yang terorganisasi untuk dapat melayani alokasi memori secara dinamis.

    Suatu heap tree adalah Complete Binary Tree (CBT) di mana harga-harga key pada node-nodenya sedemikian rupa sehingga haga-harga key pada node-node anaknya tidak ada yang lebih besar dari harga key pada node orang tuanya.

Heap dibagi atas 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.

    Contoh penggunaan heap tree dalam priority queue dapat kita lihat pada algoritma pengurutan heap sort. Algoritma pengurutan ini mengurutkan isi suatu array masukan dengan memandang array yang dimasukkan sebagai suatu Complete Binary Tree (CBT). Dengan metoda a maka Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah Complete Binary Tree (CBT) berubah menjadi suatu priority queue, maka dengan mengambil data root satu demi satu dan disertai dengan metoda d, key-key dari data root yang kita ambil secara berturutan itu akan terurut dengan output hasil pengurutan akan dituliskan dalam array hasil dari arah kanan ke kiri. Untuk optimasi memori, kita dapat menggunakan hanya satu array saja. Yaitu dengan cara memodifikasi metoda b untuk menukar isi root dengan elemen terakhir dalam heap tree. Jika memori tidak menjadi masalah maka dapat tetap menggunakan 2 array yaitu array masukan dan array hasil. 

Operasi pada Binary Heap: 

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.