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".