Heap

Halo semuanya, setelah kita belajar macam-macam balancing tree (AVL Tree, Red Black Tree, dan B-Tree), maka sekarang kita akan belajar tree yang direpresentasikan dalam bentuk array, yaitu heap.

Apa itu heap?

Heap adalah salah satu varian dari binary tree, namun Ia memiliki prinsip dan aturan sebagai berikut:

• Heap adalah binary tree yang direpresentasikan dalam bentuk array.
• Untuk melakukan traverse node dari heap, kita tidak menggunakan cara recursive, namun menggunakan proses iteratif.

Berikut ini adalah contoh gambar dari heap:

Sumber:  https://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Max-Heap.svg/1200px-Max-Heap.svg.png

Jika direpresentasikan dalam bentuk array, maka terlihat sebagai berikut:

Index	0	1	2	3	4	5	6	7	8
Value	100	19	36	17	3	25	1	2	7

Catatan: Heap selalu berupa balanced binary tree.

Heap ini memiliki 3 varian, yaitu:

·        Min heap:

Sumber: https://www.cdn.geeksforgeeks.org/wp-content/uploads/binaryheap.png

Ciri-ciri:

1. Semakin dalam depth tree ini, maka tree ini memiliki nilai yang semakin tinggi.
2. Nilai yang paling kecil adalah nilai yang berada di node paling atas, yaitu index 0

·        Max Heap:

Sumber:  https://qph.fs.quoracdn.net/main-qimg-a6a90c100e3aa52e07ba2072de7a8c7e

Ciri-ciri:

1. Semakin dalam depth tree ini, maka tree ini memiliki nilai yang semakin rendah.
2. Nilai yang paling besar adalah nilai yang berada di node paling atas, yaitu index 0

·        Min-Max Heap:

Sumber: https://www.google.co.id/url?sa=i&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FMin-max_heap&psig=AOvVaw1Frff7ejs4LT21f_WaJDP2&ust=1589548553040000&source=images&cd=vfe&ved=0CAIQjRxqFwoTCJCGrfq3s-kCFQAAAAAdAAAAABAD

Ciri-ciri:

1. Node pertama memiliki nilai min
2. Secara berselang-seling, node di ketinggian tertentu memiliki nilai yang min-max-min, dan seterusnya.

Dari gambar di atas, urutannya sebagai berikut:

• Height 0: Min
• Height 1: Max
• Height 2: Min
• Height 3: Max

Proses-proses di dalam heap:

Untuk melakukan insertion:

Contoh insert bilangan 2. Sumber: https://book.huihoo.com/data-structures-and-algorithms-with-object-oriented-design-patterns-in-c++/html/img1465.gif

• Pertama-tama, Anda mengisi value tersebut di dalam index array yang paling kanan (terakhir diisi value).
• Kedua, Anda tinggal melakukan proses traversal ke atas untuk mengecek kondisi-kondisi sesuai aturan min, max, atau min-max heap (heapify).
• Jika min, maka cek apabila node parentnya lebih besar dari childnya.
• Jika max, maka cek apabila node parentnya lebih kecil dari childnya.
• Apabila kondisi di atas terpenuhi, maka kita menukar value yang ada di child dan di parent.
• Ulangi terus sampai kondisi di atas tidak terpenuhi.

Untuk melakukan deletion (extract min/ max):

Contoh menghapus angka 2 dari heap. Sumber: https://blogger.googleusercontent.com/img/proxy/AVvXsEg0N9mgOhyphenhyphen8F-W91QS8qgR9vPhG5SHVSzGcgu2hQQYvdTaPbWRePq_JeIeTlV6pKhDv_G2efIcC3iKwVhmIMo3Y-QBKzhEOvSAJdvVSB1p1UlUm-OufrV7ICCJ9jwrXne5RZQr85KieQ5avZ3fMRzwt6xXRHDM1C8RfzOgrEvrwWQ9rC0bi4tgl9ik-IfEeUk-K_gGj1mMrOj1LWNG8mYTtFwqBB3UfoWdmlG42OWc6NuPpvLxMNkm3SoCubUb1qVtnSJ_RkQ=

• Kita bisa menukar value yang paling atas untuk kita tukar dengan value yang paling bawah (index paling kanan). Lalu, kita bisa menghapus node paling kanan dengan aman.
• Terakhir, kita harus mengecek apabila value yang barusan ditukar perlu kita traverse ulang (heapify). Pengecekannya hampir sama seperti yang di atas.
• Jika min, maka kita harus mengecek apabila value yang telah ditukar memiliki value yang lebih besar dari anakannya.
• Jika min, maka kita harus mengecek apabila value yang telah ditukar memiliki value yang lebih kecil dari anakannya.
• Ulangi terus sampai kondisi di atas tidak terpenuhi.

Satu lagi, untuk melakukan proses pengecekan ke parent maupun child, ada rumus yang bisa kita pakai:

• Any child node to parent: (current node / 2)
• Node parent to left child (2n + 1)
• Node parent to right child (2n + 2)

Aplikasi heap:

• Heap Sort
• Djikstra algorithm untuk menentukan path yang sesuai

Tries

Tries membentuk suatu pohon. Nah, tries ini memiliki bentuk yang sama dengan tree pada umumnya. Namun, hal ini sedikit berbeda, karena tries tidak boleh mengandung angka sama sekali, hanya boleh berbentuk huruf saja. Untuk mengakhiri suatu string, kita bisa menggunakan null terminator sebagai penanda. Sebagai contoh, perhatikan gambar berikut ini: 

Sumber: https://www.google.com/url?sa=i&url=http%3A%2F%2Fbtechsmartclass.com%2Fdata_structures%2Ftries.html&psig=AOvVaw0PvvzFuu9ugdXFsDyBHWio&ust=1589517590219000&source=images&cd=vfe&ved=0CAIQjRxqFwoTCJD34czEsukCFQAAAAAdAAAAABAD

Contoh di atas menggambarkan beberapa kata yang bisa kita gunakan dalam permainan word bubble. Word bubble adalah suatu game yang bertujuan agar kita bisa menebak kata-kata apa saja yang dimulai dari suatu potongan kata, misalnya hea___, maka kata-kata yang bisa kita buat adalah heap, health, heading, head, heal, dll.

Dalam tree di atas, word-word yang bisa kita bentuk adalah: Ball, Bal, Bat, Be, Cat, Rat.