Deap

Deap seakan-akan mirip dengan heap. Namun, pada kenyataannya, Deap lebih mirip dengan Min-Max Heap. Deap adalah Min-Max heap yang lebih sederhana. Bila min-max heap, min dan max nya selang-seling atas-bawah, maka dalam deap, min dan max nya ada di kiri dan di kanan.

Beberapa aturan utama mengenai Deap adalah:
1. root selalu NULL
2. left subtree dari root adalah min-heap
3. right subtree dari root adalah max-heap
4. hanya itu saja

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.

Berikut adalah contoh dari Deap:

di sini jelas kan? di sebelah kiri itu min-heap, yang di kanan itu max-heap.








Partner
Partner adalah node yang berada di posisi yang sama bila subtree min-heap dan max-heap ditumpuk menjadi 1. misalkan, node 1 partnernya 50, node 9 partnernya 12, dst.
rumus untuk mencari lokasi partnernya adalah:

min-partner = x-2^((log x) -1)
max-partner = x+2^((log x)-1)

bila lokasi partner ternyata kosong, maka partnernya menjadi parent dari posisi partner yang seharusnya.
Supaya tidak ada di awang-awang, berikut contoh penggunaannya. Kita langsung masuk ke insertion.

INSERTION

Saat sebuah data baru dimasukkan, maka akan langsung dicek dengan partnernya. Bila posisinya tertukar, maka swap, kemudian di-upheap. Jika tidak, maka langsung saja di-upheap.

berikut contohnya:

Node 17 masuk. posisinya berada di dalam min heap. Maka, nodenya langsung dicek dengan partnernya. Partner 17 harusnya berada di index ke:
16+((log 16)-1) = 24.
Tapi, karena index 24 masih kosong, maka partner 17 adalah parent dari index 24, yaitu 15.



Karena 17>15, maka swap. Kemudian, 17 di-upheap. Karena 17<40, maka tidak ada swap yang terjadi.








Lebih simpel kan, daripada min-max heap? Berikutnya mengenai deletion.

DELETION

Deletion dalam deap ada 2: delete min dan delete max. Jika delete min, maka yang dihapus adalah root dari min-heap. Bila delete max, maka yang dihapus adalah root dari max-heap.
Setelah dihapus, seperti biasa, elemen terakhir dari heap menggantikan posisi dari yang terhapus, kemudian di-downheap. Bedanya dengan heap biasa adalah setelah di-downheap, maka akan dilakukan pengecekan terhadap partner.

Berikut contohnya:
1. delete max
bosen aja delete min yang duluan. Jadi, yang kali ini max yang duluan.

saat 50 dihapus, maka 15 menggantikan posisi 50.

kemudian, 15 di-downheap biasa.

setelah di-downheap, 15 dicek dengan partnernya: 10. Bila 15<10, maka swap. Ternyata tidak. Jadi, selesai sudah proses deletion.







2. delete min
berhubung malas untuk menggambar lagi, dan sejujurnya, delete min konsepnya sama dengan delete max, maka saya hanya bisa berkata bahwa delete min dengan delete max hanya berbeda tanda saja. Tidak lebih, tidak kurang.



Jadi, sepertinya Deap hanya segini. Jauh lebih mudah daripada Max-Min Heap, kan? Jadi, kalo uda mengerti min-max heap, pasti lebih mudah untuk memahami Deap.
Sekian dulu pembahasannya sekarang. Bisa ditunggu Episode selanjutnya: "Stack and Queue"

Min-Max Heap

Bagi yang sudah mengerti prinsip dasar heap, pasti akan merasa agak rumit untuk memahami Min-Max Heap dan Deap. Apalagi bagi yang belum mengerti prinsip dasar heap. Pasti akan merasa sangat rumit untuk memahami materi ini. Jadi, yang belum mengerti prinsip dasar heap, baca saja di sini


Min-Max Heap
Min-Max Heap adalah kombinasi dari min heap dan max heap di mana masing-masing level akan berganti-ganti antara min heap dan max heap. Heap jenis ini berguna untuk langsung menemukan nilai min dan max dalam 1 heap saja.
Ini contoh min-max heap:

Gambar ini sengaja dibuat se-user-friendly mungkin.

Jadi, selang-seling antara max dan min. Simpel kan bentuknya? Tapi insertion dan deletionnya rumit bukan main. Mau coba dilihat? Persiapkan Mental dan Pikiran Anda. Here we go!

Insertion

Saat sebuah data baru dimasukkan, proses yang akan dilakukan dipengaruhi oleh lokasi data baru tersebut.
Jika data baru berada di level min, maka bandingkan dengan parentnya. Jika parent < newnode maka swap dan upheapmax dari parentnya. Jika tidak, upheapmin dari posisi newnode.
Insertion di level max berlaku hal yang serupa, namun berbeda tanda dan berbeda jenis upheap. Selebihnya, sama.
Upheap dalam min-max heap berbeda dengan upheap biasa. Upheap dalam kasus ini membandingkan dengan grandparent; bukan dengan parent.

Berikut contoh penerapannya:

angka 1 dimasukkan sebagai newnode. Karena berada di level max, maka jika 1<10, maka swap.

1 dan 10 diswap. Kemudian, dari posisi 1, di-upheapmin. karena 1<2, maka 1 dan 2 diswap.

hasil akhirnya pun menjadi begini.







Berikut contoh insertion bila dalam level min:

newnode 85 masuk di level min. Maka, 85 dibandingkan dengan parentnya (80).







ternyata 85>80, maka swap. Kemudian, 85 di-upheapmax. Tapi, karena 85<90, maka 85 tetap di posisinya.





Sejauh ini, semoga dimengerti. Bahannya memang sulit dimengerti. Namun, berusahalah. Sedikit lagi..

Deletion

Deletion dalam min-max heap ada 2: delete min dan delete max. Jika delete min, maka root langsung dihapus. Jika delete max, maka angka max dari children root akan dihapus.

Berikut penerapannya.

1. Delete min

Wolverine datang dan mencakar node 1. 1 pun hilang entah ke mana. Untuk semua children dan grandchildren nya dia meninggalkan pesan agar yang terkecil akan menggantikan dia.

80 (node terakhir), sebagai pengacara naik menggantikan 1 untuk sementara. Dia meneruskan wasiat si "1" untuk mencari anak atau cucu terkecil dan lebih kecil dari dirinya (80).


2 pun terpilih untuk menggantikan 1. Maka, 2 swap dengan 80. 80 pun mengecek kembali bilamana ada children/grandchildren dari 2 yang paling kecil dan lebih kecil dari dirinya.

10 terpilih menggantikan 80. Dan demikianlah berakhir proses downheap dari delete min.





2. delete max
mirip dengan delete min, namun semua dimulai dari level 2. Karena malas edit di paint lagi, maka sesi ini sengaja tanpa gambar. Bayangkanlah sendiri.

saat wolverine datang dan membunuh 1, ternyata cyclops datang dan ingin membunuh anak 1 yang paling besar. 100 pun dibunuhnya. Ternyata, 100 sudah meninggalkan wasiat agar anak dan cucu nya yang terbesar naik untuk menggantikan dia.

Kembali, 80 sebagai pengacara (kebetulan saja dia node paling akhir lagi), naik menggantikan 100 untuk sementara. Dia meneruskan wasiat dari almarhum 100. Anak/cucu nya yang paling besar adalah 75. Namun, karena 80 merasa 75 lebih kecil dari dia, maka 75 tidak pantas untuk menggantikan posisinya. Maka, tidak ada swap yang terjadi.

Demikianlah akhirnya 80 menjadi pewaris tahta yang ditinggalkan 100. Anak dan cucunya dibiarkan melarat.


Sekian dongeng mengenai Min-Max Heap. Semoga dapat dimengerti dan dipahami dengan baik. Semua tokoh yang terlibat tidak ada kaitannya dengan X-Men. Jangan sampai ada salah paham yang terjadi di sini. Selamat menunggu kedatangan Episode Selanjutnya: "Deap and the deap-deap durraaayyyy!!"

Heap

Heap adalah sebuah Complete Binary Tree yang memenuhi persyaratan heap. Lantas, apa itu heap? Definisi tadi tidak menjelaskan apa-apa.

Sebenarnya, heap umumnya ada 2: Min Heap dan Max Heap. Klo Min Heap, nilai parent harus lebih kecil dari nilai children. Klo, max, ya... kebalikannya.

Ini contoh min heap


Ini hanya contoh saja ya.. Memang mirip dengan BST, cuma, anak kiri ngga ada hubungannya dengan anak kanan.
Apaan tuh kotak, lingkaran, sama segitiga?
Tenang saja. Ngga ada maksud apa-apa untuk segitiga sm kotak itu. Bosan aja, tiap kali selalu lingkaran.


Ini contoh max heap

Bedanya sama Min Heap, cuma parent > children aja. Selebihnya, ngga ada bedanya sama min heap, termasuk penggunaan segitiga, kotak dan lingkaran.





Trus, untuk apa sih heap?
Heap itu gunanya supaya kita bisa "Heap-heap-huray!!". Lhoo?!
Heap itu gunanya untuk menemukan nilai max untuk max heap, dan min untuk min heap. Serasa ngga berguna kan? Tapi sangat berguna untuk membuat Priority Queue.

Heap itu sebenarnya lebih "nikmat" menggunakan array biasa dibanding pakai struct atau apalah itu. Soalnya, tiap data baru yang masuk, bakalan masuk di index paling bawah yang kosong. Jadi, penomoran indexnya, saya pakai contoh min heap di atas aja ya..
misalkan arraynya x. Maka:
x[1]=2;      x[4]=51;      x[7]=20;
x[2]=50;    x[5]=100;    dst
x[3]=4;      x[6]=10;

simpel kan? cara nyari parent sm child tinggal masukin rumus:
Index_Parent=Index/2;
Index_Child_Kiri=Index*2;
Index_Child_kanan=Index*2+1;


misalkan parentnya 100 apa?
100 kan di index 5. Jadi, parentnya pasti di index 5/2=2. jadi, 50 pasti parentnya 100. untuk child juga sama. Ingat, catat ini baik-baik: "yang dipakai dalam rumus tadi adalah index dari array nya, bukan isi arraynya"

Sampai sini clear kan? klo ngga, baca ulang aja dari atas. Klo masih ngga ngerti juga, baca di sini aja.

Saya hanya akan membahas insertion dalam min heap aja. Soalnya, max heap sama aja. Cuma beda tanda doang.

Insertion
Saat sebuah data baru dimasukkan dalam heap, maka data langsung ditempatkan di index terakhir dalam heap. Setelah itu, data di-upheap. Maksudnya, data dibandingkan dengan parentnya. Bila lebih kecil, maka swap dengan parentnya. Hal ini dilakukan sampai data tersebut lebih besar dari parentnya.
Berikut ilustrasinya:
Ini adalah kisah lanjutan dari min heap di atas.

angka 1 dimasukkan dalam heap. Maka, data tersebut di-upheap.

ternyata 1<51. Maka, 1 dan 51 di swap. Begitu pula dengan saat 1 dibandingkan dengan 50 dan dengan 2.






Maka, hasil terakhirnya akan menjadi seperti ini:










Max heap sama dengan min heap, cuma berbeda tanda. Sejauh ini jelas kan? klo, ngga, baca lagi.

Deletion
Jika dalam insertion dipakai Upheap, maka dalam deletion dipakai Downheap. Deletion dalam heap otomatis menghapus node root dari heap. Jadi, delete min dalam min heap dan delete max dalam max heap.
Dalam deletion, node paling akhir langsung menggantikan root yang didelete. Kemudian, node tersebut langsung di downheap sampai ke posisinya.

Berikut contoh dalam min-heap:
Node 1 sebagai root langsung dihapus dalam deletion.

node 51 sebagai data paling akhir langsung naik menjadi root . Node tersebut akan di-downheap; ditukar dengan min(LeftChild, RightChild) bila node < min(LeftChild, Right Child)

Sehingga min heap tersebut akan menjadi seperti gambar disamping.






Deletion dalam Max-Heap sama saja, hanya berbeda tanda saja.



Sekian mengenai Insertion dan Deletion dalam Min dan Max heap. Semoga clear dan dapat dimengerti. Mungkin kalian masih bertanya-tanya: "Ngapain repot-repot untuk nyari angka min dan max pake heap?" Tenang saja, ini masih kulit untuk Pelajaran berikutnya: "Min-Max Heap dan Deap".