Heap

Heap

Merupakan sebuah complete binary tree

Diimplementasikan menggunakan array atau linked list. Heap konsep nya sama seperti priority queue.

Kegunaan heap adalah untuk mencari elemen terkecil(min heap)/elemen terbesar(max heap)

Heap ada beberapa jenis, yaitu:

1.       Min heap : root nya merupakan elemen terkecil, dan semakin kebawah data nya semakin besar

        Contoh:

2.       Max heap : root nya merupakan elemen terbesar dan semakin ke bawah data nya semakin besar.

       Contoh:

3.       Min-Max heap : heap yang tiap level nya berselang seling min – max – min – max – dst.

        COntoh:

Min Heap & Max Heap

Cara insert:

a.       Jika min heap(elemen terkecil terletak di root):

a.       Masukkan data nya tidak seperti BST , melainkan dengan konsep array, sehingga kekanan terus, lalu kebawah, dst, atau bisa dikatakan bahwa elemen terakhir akan masuk ke index terakhir/menjadi anak paling kanan dan bawah.

b.      Data yang diinsert kemudian dibandingkan dengan parentnya, jika lbh kecil maka swap, lakukan terus menerus sampai root atau sampai data baru tersebut lbh besar dr parentnya.

b.      Jika max heap(elemen terbesar terletak di root):

a.       Masukkan data nya tidak seperti BST , melainkan dengan konsep array, sehingga kekanan terus, lalu kebawah, dst, atau bisa dikatakan bahwa elemen terakhir akan masukk ke index terakhir/menjadi anak paling kanan dan bawah.

b.      Data yang diinsert kemudian dibandingkan dengan parentnya, jika lbh besar maka swap, lakukan terus menerus sampai root atau sampai data baru tersebut lbh kecil dr parentnya.

c.       Implementasi dengan array, root itu index nya 1, bukan 0.

Perhitungan:

a.       Parent(x)             = x / 2

b.      Left-child(x)       = 2 * x

c.       Right-child(x)     = 2 * x + 1

    

Cara delete:

a.       Jika min heap(elemen terkecil terletak di root):

a.       Maka yang dihapus merupakan rootnya(elemen terkecil).

b.      Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmin(jika anak < data tsb, maka tukar,dst sampai mentok dibawah atau node tsb<anaknya).

b.      Jika max heap(elemen terkecil terletak di root):

a.       Maka yang dihapus merupakan rootnya(elemen terbesar).

b.      Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmax(jika anak > data tsb, maka tukar,dst), sampai mentok dibawah atau node tsb>anaknya).

Min-Max Heap

•       Min-Max Heap adalah kombinasi dari min heap dan max heap.

•       Masing-masing level akan berganti-ganti antara min heap dan max heap, diawali dengan min heap.

•       Heap ini berguna untuk langsung menemukan nilai min dan nilai max dalam 1 heap saja.

•       Kekurangannya heap jenis ini menemukan 1 nilai min dan 2 nilai max.

•       Pada level min semakin ke bawah nilainya semakin besar.

•       Pada level max semakin ke bawah nilainya semakin kecil.

Insert Min-Max Heap:

a.       Insert di level Min:

-          Proses Node baru yang akan dilakukan dipengaruhi oleh lokasi Node baru tersebut.

-          Jika Node baru berada di level min, maka bandingkan dengan parentnya.

                                                               i.      Jika parent < newnode maka swap dan upheapmax dari parentnya (dibandingkan dengan grandparentnya dari posisi newnode setelah swap).

                                                             ii.      Jika parent > newnode, upheapmin dari posisi newnode (dibandingkan dengan grandparentnya dari posisi newnode).

b.      Insert di Level Max:

-          Proses Node baru yang akan dilakukan dipengaruhi oleh lokasi Node baru tersebut.

-          Jika Node baru berada di level max, maka bandingkan dengan parentnya.

                                                               i.      Jika parent > newnode maka swap dan upheapmin dari parentnya (dibandingkan dengan grandparentnya dari posisi newnode setelah swap).

                                                             ii.      Jika parent < newnode, upheapmax dari posisi newnode (dibandingkan dengan grandparentnya dari posisi newnode).

Deletion pada min-max heap bisa min nya atau max nya.

Cara delete:

a.       Nilai yang dihapus diganti oleh data terakhir.

b.      Komparasi dengan grandchild baru lakukan komparasi dengan child nya terus menerus.