Algoritma Heapify adalah membangun sebuah heap dari bawah ke
atas, secara berturut-turut berubah ke bawah untuk membangun heap.
Permasalahan pertama yang harus kita pertimbangkan dalam melakukan operasi heapify adalah dari bagian mana kita harus memulai.
Bila kita mencoba operasi heapify dari akar maka akan terjadi operasi runut-naik seperti algoritma bubble sort yang akan menyebabkan kompleksitas waktu yang ada akan berlipat ganda.
Sebuah versi lain adalah membangun heap secara atas-bawah dan berganti-ganti ke atas untuk secara konseptual lebih sederhana untuk ditangani.
Versi ini mulai dengan sebuah heap kosong dan secara berturut-turut memasukkan data.
Versi lainnya lagi adalah dengan membentuk pohon heap-pohon heap mulai dari subtree-subtree yang paling bawah.
Jika subtree-subtree suatu simpul sudah membentuk heap maka pohon dari simpul tersebut mudah dijadikan pohon heap dengan mengalirkannya ke bawah.
Setelah diuji, maka ide yang paling efisien adalah versi yang terakhir, yang kompleksitas algoritmanya pada kasus terburuk adalah O(n), sedangkan versi membentuk heap tree-heap tree dari atas ke bawah kompleksitas nya O(n log n)Jadi, algoritma utama heapify adalah melakukan iterasi mulai dari internal simpul paling kanan bawah (pada representasi larik, adalah elemen yang berada di indeks paling besar) hingga akar, kemudian kearah kiri dan naik ke level di atasnya, dan seterusnya hingga mencapai akar (sebagai larik [0..N-1]). Oleh karena itu, iterasi dilakukan mulai dari j= N/2 dan berkurang satu-satu hingga mencapai j=0. Pada simpul internal tersebut, pemeriksaan hanya dilakukan pada simpul anaknya langsung (tidak pada level-level lain di bawahnya). Pada saat iterasi berada di level yang lebih tinggi, subtree subtree selalu sudah membentuk heap. Jadi, kasus akan mengalirkan simpul tersebut kearah bawah. Dengan demikian, heapify versi ini melakukan sebanyak N/2 kali iterasi, dan pada kasus yang paling buruk akan melakukan iterasi sebanyak log (N) kali.
Permasalahan pertama yang harus kita pertimbangkan dalam melakukan operasi heapify adalah dari bagian mana kita harus memulai.
Bila kita mencoba operasi heapify dari akar maka akan terjadi operasi runut-naik seperti algoritma bubble sort yang akan menyebabkan kompleksitas waktu yang ada akan berlipat ganda.
Sebuah versi lain adalah membangun heap secara atas-bawah dan berganti-ganti ke atas untuk secara konseptual lebih sederhana untuk ditangani.
Versi ini mulai dengan sebuah heap kosong dan secara berturut-turut memasukkan data.
Versi lainnya lagi adalah dengan membentuk pohon heap-pohon heap mulai dari subtree-subtree yang paling bawah.
Jika subtree-subtree suatu simpul sudah membentuk heap maka pohon dari simpul tersebut mudah dijadikan pohon heap dengan mengalirkannya ke bawah.
Setelah diuji, maka ide yang paling efisien adalah versi yang terakhir, yang kompleksitas algoritmanya pada kasus terburuk adalah O(n), sedangkan versi membentuk heap tree-heap tree dari atas ke bawah kompleksitas nya O(n log n)Jadi, algoritma utama heapify adalah melakukan iterasi mulai dari internal simpul paling kanan bawah (pada representasi larik, adalah elemen yang berada di indeks paling besar) hingga akar, kemudian kearah kiri dan naik ke level di atasnya, dan seterusnya hingga mencapai akar (sebagai larik [0..N-1]). Oleh karena itu, iterasi dilakukan mulai dari j= N/2 dan berkurang satu-satu hingga mencapai j=0. Pada simpul internal tersebut, pemeriksaan hanya dilakukan pada simpul anaknya langsung (tidak pada level-level lain di bawahnya). Pada saat iterasi berada di level yang lebih tinggi, subtree subtree selalu sudah membentuk heap. Jadi, kasus akan mengalirkan simpul tersebut kearah bawah. Dengan demikian, heapify versi ini melakukan sebanyak N/2 kali iterasi, dan pada kasus yang paling buruk akan melakukan iterasi sebanyak log (N) kali.
Sumber :
http://arraydalamprogram.blogspot.com/2010/03/heap-sort.html
Tidak ada komentar:
Posting Komentar