HeapsortHeapsort

Dr. Taufik Fuadi Abidin, S.Si., M.Tech

Irvanizam Zamanhuri, M.Sc

Jurusan InformatikaFMIPA Universitas Syiah Kuala

www.informatika.unsyiah.ac.id/tfawww.informatika.unsyiah.ac.id/irvanizam

Bahan Ajar Struktur Data dan AlgoritmaBahan Ajar Struktur Data dan Algoritma

Outline PertemuanOutline Pertemuan

Heapsort

Contoh Penggunaan

Diskusi

Sumber: http://cis.stvincent.edu/html/tutorials/swd/heaps/heaps.html

HeapsortHeapsort

Heapsort dilakukan dengan cara membangun struktur data heap dan kemudian menerapkan langkah menghapus node heap.

Pada awalnya, kondisi heap kosong. Kemudian, node heap di-insert satu per satu.

Cara alternatif adalah, menampung data yang akan diurutkan dalam array, kemudian node pada bagian root di hapus. Jika heap adalah minimal heap, maka data pada root adalah data terkecil.

Kompleksitas HeapsortKompleksitas Heapsort

Dalam kasus rata-rata atau kasus terjelek, kompleksitas dari heapsort adalah O(n log n).

Komplesitas tersebut cukup baik untuk metode pengurutan.

Pada kasus rata-rata, quicksort juga memiliki kompleksitas O(n log n), namun kadang-kadang bila kasus terjelek terjadi, kompleksitas quicksort dapat berubah menjadi O(n2).

Contoh HeapsortContoh Heapsort

Konversi array menjadi Heap. Tentukan node parent yang terakhir dalam array, yaitu (heapsize – 2)/2. Pada contoh di atas, node K adalah parent terakhir. Kemudian, lakukan FilterDown dari indeks parent terakhir s/d indeks 0. Pada contoh di atas, dari indeks 3, 2, 1, kemudian 0.

Array Array -- to to -- HeapHeap

Tree tersebut adalah Binary Tree namun belum merupakan minimal heap yang benar. Kemudian terapkan FilterDown pada node dimana parent terakhir berada, yaitu K

Lakukan FilterDownLakukan FilterDown

Setelah FilterDown selesai untuk node K, lanjutkan proses yang sama untuk indek 2 yaitu node C.

Lakukan FilterDownLakukan FilterDown

Setelah FilterDown selesai untuk node K, lanjutkan proses yang sama untuk indek 2 yaitu node C.

Lakukan FilterDownLakukan FilterDown

Setelah FilterDown selesai untuk node C, lanjutkan proses yang sama untuk indek 1 yaitu node S.

Lakukan FilterDownLakukan FilterDown

Hasil: Sebuah Heapterbentuk! Selanjutnya, remove node A menggunakan algoritma menghapus node dalam Heap.

Remove Node dari HeapRemove Node dari Heap

Remove selalu dimulai dari root karena node root adalah node dengan nilai terkecil

Masalahnya adalah bagaimana melakukan adjustment agar binary tree tetap menjadi minimal head

Algoritma: Remove node root dan ganti node tersebut dengan node pada posisi paling akhir. Kemudian fungsi FilterDown dipanggil untuk memeriksa dari root sd node leaf agar setiap node masih memenuhi syarat heap.

Remove Node Pada RootRemove Node Pada Root

Node C ditukar dengan node A, ukuran array diasumsikan berkurang 1 yaitu dari indeks 0 sd 7. Kemudian, tentukan indeks parent terakhir, dan ulangi proses .

Hasil AkhirHasil Akhir

Data yang terurut descending order

Questions &

Discussion