Heap , Deap !

HEAP
Heap merupakan salah satu proses yang ada dalam Binary Search Tree.
Heap sendiri dibedakan menjadi 3 macam:
       -Min Heap.
       -Max Heap.
       -Min-Max Heap.
Dalam Heap dibedakan menjadi 2 macam Proses : Insertion, dan Deletion.

Min Heap : Memiliki ciri-ciri sebagai berikut;
       -Setiap elemen Node yang ada harus lebih kecil dari elemen Children(anaknya).
       -Elemen Node yang terkecil terletak pada ROOT.
       -Elemen Node yang terbesar terletak pada salah satu node yang ada di LEAVES.





Berikut adalah konsep Insertion dalam Heap
 
 kita akan memasukkan angka dengan value 2
Pertama-tama yang angka 2 akan dimasukkan ke dalam index angkat terakhir yang ada dalam tree tersebut. Angka 2 akan dimasukkan ke sebelah 8. (selalu diinsert dari node dengan index terakhir).



Disini, pengecekan dilakukan karena ciri-ciri dari heap adalah setiap Node yang ada selalu lebih kecil dari Node anaknya (children). value angka 2 lebih kecil dari parentnya yaitu 6. Maka karena 6 > 2 , angka 2 akan naik dan mereplace kedudukan 6 dan berlaku sebaliknya.




Disini pengecekan pun berhenti karena angka 2 lebih besar dari parent Nodenya yaitu 1. maka insertion dalam Min heap pun telah selesai.

Deletion


Deletion pada root.
Pertama , Root akan dihapus, lalu penggantian akan dilakukan terhadap INDEX terakhir dalam tree. Maka angka 8 akan meng-replace angka 1(yang akan di delete).

Namun, karena ciri2 dalam heap tidak di penuhi dari tree tsb, karena nilai ROOT nya lebih besar dari children yang ada maka pengecekan dilakukan


Karena nilai 8 lebih besar dari nilai 3, maka di swap. dan proses ini dilakukan terus menerus sampai tree tersebut memenuhi syaratnya

Max Heap
Proses yang ada dalam Max Heap hampir sama dengan Min Heap, hanya pembalikan saja. Dimana ROOT memiliki value yang paling besar, sedangkan leave memiliki value kecil.




Konsep Insertion dan deletion juga berlaku sama dengan Min heap , namun value yang besar lebih di prioritaskan dari pada yang kecil.

Min - Max Heap


Min Max Heap, memiliki konsep dimana, setiap level ganjil dimulai dengan MIN, dan level genap dimulai dengan MAX heap.  Maka, value terkecil terletak dalam ROOT.

Deap

Deap memiliki konsep yang sama heap, lebih tepatnya min-max heap yang lebih sederhana.
Berikut adalah aturan aturan yang ada dalam Deap:
1. root selalu NULL
2. left subtree dari root adalah min-heap
3. right subtree dari root adalah max-heap

Sesuatu yang unik dari deap adalah sesuatu yang bernama "partner". Partner adalah pasangan dari sebuah node dari deap.  Di bawah akan dijelaskan dengan lebih detail mengenai partner. 



Yang dimaksud adalah, lihat bagian tree sebelah kiri, jika diperhatikan bagian kiri memiliki MIN HEAP sedangkan bagian sebelah kanan memiliki MAX HEAP.
Partner adalah Node yang berdampingan dari MIN heap ke Max Heap, contohnya pada gambar sebelah kanan bisa dilihat, bahwa PARTNER dari angka 10 adalah 50, angka 12 dengan 40 dan angka 25 dengan Node yang kosong.
Bila lokasi partner ternyata kosong, maka partnernya menjadi parent dari posisi partner yang seharusnya.


Nama : Dickson
NIM : 1701291283
Binus University