Jadi kali ini saya belajar tentang Heap dan Trie namun disini saya akan menjelaskan tentang Heap.
Heap Mirip seperti Array
Jadi apabila kita akan memasukan angka angka ke dalam heap maka akan dimasukan ke sebuah array contohnya seperti = 2,5,10,15,4,9
lalu Heap sendiri itu ada 3 yaitu Min Heap, Max Heap, Min-Max Heap.
Heap sendiri ada cara mencari parentnya dari current node
jika bukan array ke 1 yang adalah root maka cara mencari parentnya adalah = array indx ke ... (curr) / 2
dengan catatan index parentnya yang di temukan di simpan dalam integer.
Jadi apabila index ke 2 parentnya adalah index ke 1 karena 2/2 berlaku juga untuk index ke 3 yaitu parentnya index ke 1 dengan cara 3/2 = 1.5 karena dalam int maka hasilnya menjadi 1
Lalu untuk mencari left child dan right child dari sebuah node misal node di index ke 1 adalah left childnya tinggal di kali 2, lalu right childnya = (index node sekarang *2) + 1
Min Heap & Max Heap Insertion & Deletion
Apabila kita akan memasukan angka ke Min Heap maka ada namanya UpHeap dan DownHeap
Up Heap
membandingkan node yang sekarang dengan parentnya sesuai dengan apa yang di butuhkan apabila Min heap maka yang lebih kecil akan naik, namun sebaliknya apabila Max heap maka yang lebih besar yang akan naik. Ini digunakan saat Insertion Min Heap maupun Max Heap
Down Heap
membandingkan parent dengan right child dan left child dan berfungsi pada saat Deletion di Min Heap maupun Max Heap
Contoh kita akan menginsert 3 ke sebuah array 4,5,6 dan diharuskan menggunakan MIN Heap maka pertama tama akan dimasukan sehingga menjadi seperti 4,5,6,3 namun akan di cek menggunakan Up Heap maka karena 3 lebih kecil dibanding parentnya yaitu 6 maka akan bertukar lalu di cek lagi 3 lebih kecil dibanding parentnya yaitu 4 maka arraynya akan menjadi 3,5,4,6
untuk MAX Heap konsepnya sama hanya berbeda saat di cek yaitu lebih besar dan lebih kecilnya
lalu untuk deletion adalah dengan menggunakan Down Heap dan contohnya adalah apabila kita akan mendelete angka 3 dari array 3,5,4,6 maka angka terakhir di array akan naik ke atas menggantikan angka 3 sehingga menjadi 6,5,4 sedangkan kita maunya MIN Heap maka akan dilakukan Down Heap dengan membandingkan nilai paling kecil dari childnya untuk menggantikan si 6 ini sehingga arraynya menjadi 4,5,6
Sekian dari saya untuk kali ini.
Heap Mirip seperti Array
Jadi apabila kita akan memasukan angka angka ke dalam heap maka akan dimasukan ke sebuah array contohnya seperti = 2,5,10,15,4,9
lalu Heap sendiri itu ada 3 yaitu Min Heap, Max Heap, Min-Max Heap.
Heap sendiri ada cara mencari parentnya dari current node
jika bukan array ke 1 yang adalah root maka cara mencari parentnya adalah = array indx ke ... (curr) / 2
dengan catatan index parentnya yang di temukan di simpan dalam integer.
Jadi apabila index ke 2 parentnya adalah index ke 1 karena 2/2 berlaku juga untuk index ke 3 yaitu parentnya index ke 1 dengan cara 3/2 = 1.5 karena dalam int maka hasilnya menjadi 1
Lalu untuk mencari left child dan right child dari sebuah node misal node di index ke 1 adalah left childnya tinggal di kali 2, lalu right childnya = (index node sekarang *2) + 1
Min Heap & Max Heap Insertion & Deletion
Apabila kita akan memasukan angka ke Min Heap maka ada namanya UpHeap dan DownHeap
Up Heap
membandingkan node yang sekarang dengan parentnya sesuai dengan apa yang di butuhkan apabila Min heap maka yang lebih kecil akan naik, namun sebaliknya apabila Max heap maka yang lebih besar yang akan naik. Ini digunakan saat Insertion Min Heap maupun Max Heap
Down Heap
membandingkan parent dengan right child dan left child dan berfungsi pada saat Deletion di Min Heap maupun Max Heap
Contoh kita akan menginsert 3 ke sebuah array 4,5,6 dan diharuskan menggunakan MIN Heap maka pertama tama akan dimasukan sehingga menjadi seperti 4,5,6,3 namun akan di cek menggunakan Up Heap maka karena 3 lebih kecil dibanding parentnya yaitu 6 maka akan bertukar lalu di cek lagi 3 lebih kecil dibanding parentnya yaitu 4 maka arraynya akan menjadi 3,5,4,6
untuk MAX Heap konsepnya sama hanya berbeda saat di cek yaitu lebih besar dan lebih kecilnya
lalu untuk deletion adalah dengan menggunakan Down Heap dan contohnya adalah apabila kita akan mendelete angka 3 dari array 3,5,4,6 maka angka terakhir di array akan naik ke atas menggantikan angka 3 sehingga menjadi 6,5,4 sedangkan kita maunya MIN Heap maka akan dilakukan Down Heap dengan membandingkan nilai paling kecil dari childnya untuk menggantikan si 6 ini sehingga arraynya menjadi 4,5,6
Sekian dari saya untuk kali ini.
Komentar
Posting Komentar