Heap & Tries

HEAP

heap adalah Complete Binary Tree(CBT) dimana harga-harga key pada node-nodenya sedemikian rupa sehingga harga-harga key pada node-node anaknya lebih kecil dari orang tuanya ataupun juga bisa lebih kecil dari orangtuanya. kedua jenis tersebut adalah max heap dan min heap.

Min-Heap

di heap ini, data pada node lebih kecil dari pada pada anaknya. Node ini memiliki node dengn nilai terkecil dengan letak pada root dan node terbedar terletak pada leaf. Heap dapat diimplementasikan dengan linked list tapi akan lebih mudah jika menggunakakn array.berikut contoh min-heap.

didalam Min-Heap terdapat beberapa operasi yaitu
-Find-min: mencari data terkecil pada Min-Heap(Root).
-Insertion:
 1. insert data baru sebagai node terakhir dari heap.
 2. lakukan Up-Heap
     bandingkan nilai data yang di-insert dengan parentnya. jika lebih kecil dari parent, maka tukar            nilainya
 3. Uphead dihentikan jika nilai parentnya lebih kecil dari current node atau jika current node adaah        root
-Deletion:
 1. Tukar nilai dari data terakhir dengan root. Root sebagai current node.
 2. karena data yang ingin dihapus sekarang berada pada leaf, langsung hapus.
 3. lakukan Down-Heap
      bandingkan nilai current node dengan kedua anaknya. jika salah satu anaknya lebih kecil dari             current node, tukar posisi. jika kedua anaknya lebih kecil nilainya dari current node,tukar posisi           dengan anak yang nilainya paling kecil.
 4. Down-Heap dihentikan jika current node bernilai lebih kecil dari kedua anaknya atau jika current        node adalah leaf.

Max-Heap
Max-Heap merupakan kebalikan dari Min-Heap dimana data pada node lebih besar dari data pada anaknya. di heap ini, node dengan nilai terbesar terletak pada root sedangkan node dengan nilai terkecil terletak pada leaf. operasi pada Max-Heap hampir sama dengan operasi pada Min-Heap. yang membedakan hanya konsepnya saja(data terbesar ada pada root, parent lebih besar dari anak). berikut contoh dari Max-Heap



Min-Max Heap

kondisi ini merupakan kondisi pada head bergantian antara minimum dan maximum antar level. element pada lebel genap bernilai lebih kecil dari anaknya, sedangkan element pada level ganjil bernilai lebih besar dari anaknya. root memiliki nilai paling kecil dan kedua anaknya memiliki nilai paling besar. berikut contoh dari Min-Max Heap:
operasi operasi pada Min-Max Heap

• insertion

          1. insert data baru sebagai node terakhir dari heap

          2. lakukan upheap

          proses upheap pada Min-Max Heap:

             - jika node baru ada pada Min-Level:

                1. jika parent dari node baru lebih kecil dari node baru tersebut maka tukar nilai dan                                 upheadmax dari parent.

                2. selain diataas, upheadmin dari node baru.

             - jika node baru ada pada Max-Level:

                1. jika parent dari node baru lebih besar dari node baru tersebut maka tukar nilai dan                                 upheapmin dari parent

                2.  selain diatas, upheapmax dari node baru.

             - Upheadmin:

                1. bandingkan nilai dari current node dengan nilai dari grand-parent.

                2. jika nilai dari current node lebih kecil dari parentnya, maka tukar niai.

             - Upheapmax

                1. bandingkan nilai dari current node dengan nilai dari grand-parent.

                2. jika nilai dari current node lebih besar dari parentnya, maka tukar nilai.

• deletion

         - deletion dari data terkecil:

            1. tukar ilia root dengan nilai dadri data terakhir pada heap.

            2. hapus data terakhir.

            3. downheapmin dari root.

         - deletion dari data terbesar:

            1. tukar nilai anak kiri atau anak kanan dari root dengan nilai dari data terakhir pada heap.

            2. hapus data terakhir.

            3. downheapmax dari node.

         - downheapmin

            -  m adalah anak dengan nilai terkceil dari current node dan grand children.

            - jika m adalah grand children dari current node, maka:

               + jika m lebih kecil dari current node, maka:

                  1. tukar nilainya

                  2. jika m lebih besar dari parentnya maka tukar nilainya.

                  3. lanjutkan downheapmin dari m.

            - jika m adalah children dari current node, maka:

               + jika m adalah children dari current node, maka:

                  1. tukar nilainya.

         - downheapmax

            kebalikan dari downheapmin.

Tries 

 tries adalah tree yang dilakukan untuk menyimpan array asosiatif. properties pada tries adalah setip vertex/node merepresentasikn satu huruf dan root merepresentasikan karakter kosong. aplikasi pada trees adalah fitur auto complete yang ada pada web browser. berikut contoh dari tries:

Daftar Pustaka:
http://gabrielyakub.blogspot.com/2016/05/pertemuan-8-heap-tries-hashing.html?view=timeslide
http://prillysia.blog.binusian.org/tag/heap/