Heaps adalah salah satu jenis struktur data yang menggunakan konsep perfect binary tree sebagai dasarnya. Meskipun secara dasarnya menggunakan konsep binary tree, implementasi heap biasanya dilakukan menggunakan array, hal tersebut karena dengan menggunakan array akan lebih mudah untuk dilakukan dan karena heap sendiri memiliki aturan penyimpanan data yang sedikit berbeda daripada binary tree pada umumnya. Untuk melihat perbedaannya bisa dilihat gambar dibawah ini :
Bisa dilihat bahwa tree diatas terlihat aneh dan tidak sesuai dengan aturan binary tree pada biasanya. Bentuk Tree diatas disebut dengan nama Max Heap. Max Heap sendiri adalah salah satu jenis dari heap. Heap diimplementasi menggunakan array, namun yang perlu diingat penyimpanan data pada heap dimulai dari index 1, alasannya untuk mempermudah pencarian untuk left right dan parentnya.
Jenis Heap sendiri dibagi menjadi 3 yaitu :
- Min Heap
Min Heap adalah Heap yang dimana nilai teratas/parentnya lebih kecil daripada childnya, contohnya sebagai berikut :
Dapat dilihat bahwa di root heap tersebut adalah nilai terkecil dari keseluruhan heap. Perlu diingat bahwa aturan pada heap berbeda dengan binary tree. Bisa dibilang pada heap untuk urutannya berjalan secara vertikal (per level) dan bukan seperti tree yang memecah ke kiri dan kanan tergantung nilainya. Oleh sebab itu hal diatas seperti 2 menjadi left childnya 1 dan 3 menjadi right childnya 1 bisa terjadi di heap karena heap tergantung dengan urutan input (bisa diimplementasi menjadi priority queue).
- Max Heap
Dapat dilihat bahwa semakin kebawah nilai semakin mengecil. Urutannya pun juga terlihat acak karena bergantung dari urutan input, tetapi untuk hubungan parent dan child di tiap node masih memenuhi aturan.
- Min Max Heap
Heap jenis ini bisa dibilang merupakan campuran antara min heap dan max heap. Hal yang membuat jenis heap ini unik adalah datanya selang seling tiap level/tingkatannya. Aturannya adalah untuk tingkat ganjil bersifat minimum, sedangkan genap bersifat maximum. Berikut contohnya :
Dapat dilihat di contoh diatas bahwa pada level 1 terdapat nilai 7 yang merupakan nilai terkecil dari heap ini, kemudian left childnya yaitu nilai 70 adalah nilai terbesar dari heap ini. Maka bisa dibilang bahwa nilai di root adalah nilai terkecil dari heap, sedangkan salah satu child dari root adalah nilai maksimum dari heap.
Operasi-operasi pada heap :
Insertion :
Proses insertion pada heap menggunakan index seperti pada array. Jadi inputnya dari index terakhir kali inputan dimasukkan. Kalau seperti itu, bagaimana relasinya bisa menyerupai tree ? Nah, untuk menentukan mana parent, left child, dan right childnya maka digunakan pattern sebagai berikut :
(n=index node saat ini)
Untuk mencari parent suatu node, indexnya adalah : n/2 (catatan indexnya harus integer).
Untuk mencari left child suatu node, indexnya adalah : 2*n.
Untuk mencari right child suatu node, indexnya adalah : 2*n +1.
Sebagai contoh data ke 2 dari suatu heap parentnya adalah data ke 1 karena data ke 2 adalah left childnya data ke-1. Kalau ingin mencari parentnya data ke-2 dengan rumus diatas maka : 2/2 = data ke 1. Begitu juga sebaliknya untuk mencari left child data 1 dengan rumus diatas maka : 2*1 = data ke 2.
Berdasarkan gambar, right childnya data ke 1 adalah data ke 3. Mari kita buktikan dengan rumus diatas : 2*1 +1 = 3. Maka right childnya data 1 adalah data ke 3. Untuk parent data 3 pun dapat dicari dengan cara : 3/2 = 1 (Integer). Sehingga parent data 3 terbukti data ke 1.
Setelah dilakukan insertion seperti itu, hal yang dilakukan berikutnya adalah melakukan upHeap / Heapify Up. Berikut penjelasannya :
Kalau kita lihat contoh diatas, bisa dilihat bahwa kita memasukkan angka 25 ke heap tersebut. Berdasarkan aturan index tadi maka 25 menjadi child dari node 90. Jenis heap diatas adalah min heap, sehingga aturannya adalah nilai parent harus lebih kecil dibanding kedua childnya. Akan tetapi, dengan dimasukkan angka 25, maka aturan tersebut terlanggar karena 25 lebih kecil dari 90 tetapi 90 berada diatas 25. Untuk menyelesaikannya, kita harus menukar nilai dari child dan parentnya.
Proses penukaran inilah yang disebut dengan UpHeap/ Heapify Up. Caranya dengan membandingkan node yang baru masuk dengan parentnya (sekaligus dengan grandparentnya jika min-max heap). Aturan penukarannya tergantung jenis heapnya (parentnya lebih besar dari node jika min heap, parentnya lebih kecil dari node jika max heap). Proses penukaran ini dilakukan sampai aturannya tidak terlanggar atau node sudah di posisi root.
Deletion :
Proses deletion pada heap umumnya menghapus node paling atasnya terlebih dahulu, kemudian digantikan nilainya dengan node index terakhir dimasukkan, kemudian menghapus node terakhir tersebut. Berikut contohnya :
Pada gambar diatas adalah proses delete pada heap. Pada heap biasa (bukan modifikasi) proses delete dilakukan dari root, sehingga pada gambar diatas node yang dihapus adalah node 4. Seperti aturan yang sudah disebut diatas, nilai yang akan menggantikan nilai root sebelumnya adalah nilai di node urutan paling terakhir dimasukkan, dalam kasus ini node 8. Lokasi node 8 sendiri seolah dihapus/dibuat NULL. Setelah proses penggantian tersebut, kita perlu mengecek kondisi heap apakah masih sesuai dengan heap yang kita buat.
Untuk heap ini yaitu min heap, masih terlihat bahwa 8 bukanlah nilai terkecil dari heap. Untuk mengembalikan menjadi status heap, maka perlu dilakukan penukaran nilai dengan childnya. Proses penukaran ini disebut dengan DownHeap / Heapify Down. Prosesnya dilakukan dari node pengganti root kemudian bandingkan dengan child terkecilnya/terbesarnya tergantung tipe heapnya (dari antara 2 childnya cari yang paling memenuhi). Jika sudah ditemukan, posisi mereka ditukar lalu dicek lagi di posisi barunya yang sekarang apakah child dibawahnya masih belum memenuhi aturan heap. Proses DownHeap ini dilakukan sampai posisinya kembali menjadi heap/nodenya berada di posisi leaf.
Implementasi Heap : Heap Sort
Seperti yang kita ketahui, heap ini direpresentasikan dalam array seperti ini :
Seperti yang kita lihat juga bahwa pada heap tidak terlihat ada urutan yang jelas, namun berdasarkan aturan min heap atau max heap tetap memenuhi syarat. Nah, bagaimana jika kita ingin membuat heap secara berurutan (misalnya dari kecil ke besar dan sebaliknya) dan tetap masih mengikuti aturan heap ?
Untuk itulah ada yang namanya Heap Sort, berikut ilustrasinya :
HeapSort sendiri ada 2 jenis, yaitu secara ascending (dari kecil ke besar) dengan menggunakan kaidah min heap dan secara descending (dari besar ke kecil) dengan kaidah max heap.
Sebagai contoh saya menggunakan aturan max heap. Pada dasarnya, proses Heap Sort ini sebenarnya adalah proses melakukan delete berulang-ulang sampai heap habis yang dimana data yang di delete ditampung di array lain. Kemudian setelah heap kosong, array lain yang menampung data di delete akan menjadi berurutan dan bisa dicopy kembali ke array heap sebelumnya.
Saya akan menjelaskan alurnya, pada contoh diatas merupakan max heap sehingga proses deletion akan menghapus node 16 dan berdasarkan cara deletion nilai 16 akan digantikan dengan angka 1 yang kemudian dilakukan downheaping sampai akhirnya nilai root adalah 14. Nilai 16 ini ditampung di suatu array baru sementara (dalam kasus contoh diatas node 16 diletakkan di akhir array, sehingga setelah jadi akan membentuk sorting secara ascending). Kemudian proses berikutnya adalah delet 14 dan proses delete dilakukan berulang-ulang sampai heap habis. Jika mengikut pattern seperti ini, array penampung akan menjadi berurutan dan hal inilah yang disebut Heap Sort. Jika dimasukkan kembali ke dalam bentuk tree akan terlihat bahwa data sudah berurutan dari kiri kanan dan secara vertikal sesuai dengan aturan heap.
Tries
Tries adalah jenis struktur data yang membentuk trees bercabang-cabang yang didalamnya merupakan kumpulan karakter-karakter yang membentuk suatu kata. Tries ini biasanya digunakan untuk fitur autocomplete, spell checker dari kamus, atau mencari validitas suatu kata.
Berikut adalah gambaran Tries :
Jika dilihat dari ilustrasi diatas, bisa diketahui bahwa konsep tries ini memiliki fungsi untuk mempermudah dalam proses pencocokan kata dalam waktu yang singkat. Hal ini dikarenakan adanya rute rute yang memecah yang kemudian membentuk kata yang baru dan unik. Sebagai contoh pada rute r-o ada 2 branch, yaitu rute l-l dan rute u-n-d. Kedua rute ini membentuk suatu kata yang berbeda, tetapi dalam proses pencocokannya hanya perlu dilakukan pencarian sebanyak panjang kata tanpa perlu mengeceknya dari awal setiap pengecekan. Hal ini akan sangat membantu jika ada banyak kata yang memiliki beberapa huruf yang sama namun memiliki akhiran berbeda/panjangnya berbeda.
Tries ini sendiri bisa tidak terbatas jumlahnya tergantung seberapa banyak kita ingin memasukkan data. Sebagai contoh, kita bisa menambahkan kata "read" pada Tries diatas. Hal tersebut dapat dilakukan dengan membuat branch baru pada node 'r' kemudian membuat rute baru yaitu 'e-a-d'. Dengan begitu sudah dibentuk Trie baru tanpa perlu membuat dari awal lagi.
Bisa diperhatikan bahwa di beberapa node ada tulisan isFinal. Apakah isFinal itu ?
isFinal ini adalah suatu variabel boolean yang menandakan akhir dari suatu kata yang memiliki arti. Jika isFinal true maka dari awal sampai node tersebut telah terbentuk suatu kata, meskipun Trienya sendiri masih ada lanjutannya. Jadi apabila traversal berhenti di node yang memiliki tulisan isFinal dan kata yang dicari/dimasukkan sesuai maka pencarian berhenti dan tidak dilanjutkan kebawah. Dalam satu rute bisa saja banyak node yang memiliki isFinal karena pada node tersebut telah terbentuk kata yang baru.
Kesimpulannya, adanya Tries ini mempermudah dalam proses pencarian/pencocokan kata terutama kata pada kamus.
Sekian materi mengenai Heap dan Tries ini. Semoga materi ini bermanfaat bagi para pembaca.
Tidak ada komentar:
Posting Komentar