Heap

Pengertian Heap :

Sebuah Complete Binary Tree dimana semua node pohon berada dalam urutan tertentu.

Heap dapat diimplementasikan menggunakan linked-list tapi lebih mudahnya mengimplementasikan menggunakan array.

Heap dibagi menjadi 3 jenis :

1. Min-Heap :

- Tersusun dari tree yang tiap element nodenya lebih kecil daripada element anaknya. Pada bagian root tree (level 0) adalah bagian element yang paling kecil  sedangkan bagian element yang terbesar berada di suatu tempat di bagian element terakhir(leaves node).

 - Contoh Min-Heap :

 - Insert Min-Heap :

Jika ada element baru yang masuk, maka insert element baru ke bagian akhir heap(setelah index element node terakhir). Lakukan uphead pada element baru(memperbaiki bagian tree supaya sesuai).

 Uphead dilakukan dengan membandingkan element yang baru kita insert dengan nilai parentnya lalu :

1. Apabila nilai baru yang baru kita insert lebih kecil dari parentnya maka tukar nilai mereka dan teruskan uphead node parentnya.

2. Berhenti jika nilai parentnya lebih kecil daripada nilai node saat ini atau node saat ini adalah root(tidak memiliki induk).

Contoh insert pada Min-Heap :

- insert node baru (20)

 -Insert node baru (5)

 

lakukan uphead

- Delete pada Min-Heap :

Jika delete, kita menghapus nilai yang terkecil pada tree yaitu yang berada pada root. Nilai root yang dihapus digantikan dengan element terakhir pada heap. Lalu kurangi jumlah element pada heap. Setelah itu lakukan downHeap.

DownHeap dilakukan dengan membandingkan nilai node saat ini(dimulai dari root) dengan nilai pada node anak kiri dan kanan. Lalu :

1.  Tukar node saat ini dengan nilai node yang terkecil pada node anak dan teruskan downheap pada node anak tersebut

2. Stop jika nilai node saat ini lebih kecil dibandingkan kedua nilai anaknya atau node saat ini adalah leaf ( tidak punya anak). 

2. Max-Heap :

 Tersusun dari tree yang tiap element nodenya lebih besar daripada element anaknya. Pada bagian root tree (level 0) adalah bagian element yang paling besar sedangkan bagian element yang terkecil berada di suatu tempat di bagian element terakhir(leaves node).

 - Contoh Max- Heap:

- Insert dan Deletion pada Max-Heap aturannya sama hanya diubah lebih kecil menjadi lebih besar saja. 

3. Min-Max Heap : 

 Kondisi tree dimana diantara minimum dan maksimum pada setiap level. Setiap element pada level genap/ganjil adalah terkecil daripada  semua node anak-anaknya(min-level). Sebaliknya setiap element pada level ganjil/grnap adalah terbesar daripada  semua node anak-anaknya(max-level). 

 

- Insert Min-Max Heap :

masukan element baru ke bagian akhir dari heap. lalu lakukan uphead pada element baru. Namun uphead pada min-max sedikit berbeda dengan min-heap atau max-heap. 

Uphead pada min-max ada ketentuan sebagai berikut :

1. Jika node baru berada di level min maka :

 - Bandingkan dengan orangtua node baru. apabila node orangtua node baru nilainya lebih kecil dari node baru maka tukar nilai mereka dan lakukan upheadmax dari parentnya.

-Atau  lakukan upheadmin  dari node baru

2. Jika node baru berada di level max maka :

 - Bandingkan dengan orangtua node baru. apabila node orangtua node baru nilainya lebih besar dari node baru maka tukar nilai mereka dan lakukan upheadmin dari parentnya.

-Atau  lakukan upheadmax  dari node baru.

Upheadmin adalah membandingkan node saat ini dengan nilai node pada grandparentnya. Jika nilai node saat ini lebih kecil daripada pada node parentnya maka tukar nilai mereka dan lanjutkan upheadmin node grandparent.

Upheadmax adalah membandingkan node saat ini dengan nilai node pada grandparentnya. Jika nilai node saat ini lebih besar daripada pada node parentnya maka tukar nilai mereka dan lanjutkan upheadmax node grandparent.

- Contoh insert min-max heap :

 1. Insert 50

Upheapmax : karena node 50 tidak mempunyai grand-parent,proses selesai.

2. Insert 5 

 

Upheapmin : node 5 lebih kecil daripada nilai parent, maka tukar nilai mereka and lanjutkan upheapmin 

 

Upheapmin : node 5 lebih kecil daripada nilai parent, maka tukar nilai mereka and lanjutkan upheapmin 

 

Upheapmin : karena node 5 tidak mempunyai grand-parent, proses selesai.

- Deletion Min-Max Heap 

ada ketentuan yaitu :

           1. Menghapus element terkecil 

                  •Gantikan nilai root dengan nilai element terakhir pada heap. 

                  •Kurangi jumlah element pada heap 

     •Downheapmin dari root.    
2. Menghapus element terbesar :

    • Gantikan nilai baik pada node anak kiri or node anak kanan pada root (tergantung pada nilai mana yang paling besar) dengan element terakhir pada heap.

     • Kurangi jumlah element pada heap

                  • Downheapmax dari node.

Downheapmin pada Min-max heap :
• Misalkan m adalah element terkecil pada node anak saat ini dan grandchildren (jika ada).  
• Jika m adalah grandchildren dari node saat ini maka 
   - Jika m nilainya lebih kecil dibanding node saat ini 
• Tukar nilai mereka 

          • Jika m nilainya lebih besar daripada nilai node orangtuanya maka tukar nilai mereka

          • Lanjutkan downheapmin dari m 

• Jika m adalah anak dari node saat ini maka 

     - Jika m nilainya lebih kecil daripada node saat ini maka tukar nilai mereka 

Downheapmax pada Min-Max heap sama seperti downheapmax hanya diganti element terkecil menjadi element terbesar.

Contoh deletion pada Min-Max Heap :

1. Delete Max :

Hapus nilai terbesar yaitu 50 lalu tempat nilai 50 digantikan dengan nilai terakhir dari node yaitu 14   

 

Downheapmax : cari nilai terbesar dari node anak-anaknya dan node grand-childrennya. Setelah itu tukar nilai  mereka.

 

Downheapmax : karena node parent 14 nilainya lebih besar dari 14, maka tukar nilai mereka dan lanjutkan downheapmax.

 

Karena 28 tidak mempunyai anak ataupun grand-children maka proses selesai.

Referensi :

https://upload.wikimedia.org/wikipedia/commons/thumb/5/50/Min-max_heap.jpg/300px-Min-max_heap.jpg 

https://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Max-Heap.svg/240px-Max-Heap.svg.png

PPT Binus-Heap&Tries