Heap dan Deap

HEAP

Tree yang cara masukkin datanya berbeda dari BST, ada 3 macem yaitu Min Heap, Max Heap, dan Min Max Heap.

Index nya Left Child = 2n, kalo Right Child = 2n+1.

Min Heap

Data yang ada di root itu adalah data yang paling kecil, makin ke bawah makin gede.

Insertion di heap itu caranya, data masuk ke paling bawah. Lalu di cek sama parentnya.

Misal, kek contoh di atas itu insert 20. Masuk ke tempat paling bawah dan masuknya dari kiri ke kanan. Abis masuk di cek sama Parent-nya. Kalo Parent-nya lebih besar, dituker (karena ini Min Heap). Dan di cek terus sampe Parent-nya lebih kecil dari yang di-insert itu sendiri.

Deletion di heap, data yang mau dihapus nanti nya diganti sama data yang ada di paling bawah. Lalu di cek lagi sama Child-nya. Kalo ada Child yang lebih kecil, dituker. Contohnya kek gini nih

Max Heap

Insertion dan Deletion nya sama persis kek Min Heap, Cuma dibalik aja. Kalo di Max Heap, root nya itu adalah data paling besar. Makin ke bawah datanya akan semakin kecil.

Contoh Max Heap nih..

Min Max Heap

Heap yang ini kek campuran-nya Min Heap sama Max Heap. Jadi dalem 1 tree, Min Heap dan Max Heap saling selang seling. Biar lebih gampang liat gambar-nya aja…

Insertion dan Deletion-nya sama aja, Cuma tergantung tempat di Insert atau Delete nya aja..

Deap

Disebut juga Double Ended Heap.

Nah disini ga ada macem-macemnya kek Heap, kalo di Deap, root nya itu adalah data kosong.

Left Childnya (Yang dari Root doang) itu make prinsip Min Heap, sedangkan Right Childnya (Yang dari Root doang) make prinsip Max Heap.

Insertion dan Deletion-nya pun rada beda dari Heap, karena harus dibandingin dengan Partner-nya dulu setelah di Insert atau Delete.

Misal kek gambar di atas, Partner-nya ditentuin dari warnanya. Nah kenapa angka 30 dan 9 partnernya 40?? Karena di Seberangnya (Right Child dari Root), belum ada data yang setara dengan mereka. Karena itu Partner mereka adalah Partner dari Parent-nya mereka.

Nah buat penjelasan yang lebih lengkap tentang Insertion dan Deletion di Deap ini, lebih baik kalian tanyakan ke dosen masing-masing. Karena saya juga masih ragu sama cara yang saya gunakan, dari pada sesat kan…….

Krisna

1701290236

02PGT

www.skyconnectiva.com || www.binus.ac.id