Heapsort

Dalam pemrograman komputer, heapsort adalah algoritma sorting-perbandingan berbasis. Heapsort dapat dianggap sebagai peningkatan semacam seleksi: seperti algoritma itu, membagi input menjadi diurutkan dan wilayah disortir, dan iteratif menyusut wilayah disortir dengan mengekstraksi elemen terbesar dan bergerak yang ke wilayah diurutkan. Peningkatan tersebut terdiri dari penggunaan struktur data tumpukan daripada pencarian linear-waktu untuk menemukan maksimal.

Meskipun agak lambat dalam praktek pada kebanyakan mesin dari quicksort yang dilaksanakan, ini memiliki keunggulan yang lebih menguntungkan terburuk O (n log n) runtime. Heapsort adalah algoritma di tempat, tapi itu bukan semacam stabil.Heapsort diciptakan oleh JWJ Williams pada tahun 1964. 

Hal ini juga kelahiran tumpukan, disajikan sudah oleh Williams sebagai struktur data yang berguna dalam dirinya sendiri. [4] Pada tahun yang sama, RW Floyd menerbitkan sebuah versi perbaikan yang bisa mengurutkan array di tempat, melanjutkan penelitian sebelumnya ke dalam algoritma Treesort.

 Algoritma heapsort sendiri memiliki O (n log n) kompleksitas waktu baik menggunakan versi heapify. 

procedure heapify(a,count) is (end is assigned the index of the first (left) child of the root) end :=
 1) while end < count (sift up the node at index end to the proper place such that all nodes above          the end index are in heap order) siftUp(a, 0, end) end := end + 1 (after sifting up the last node all nodes are in heap order) procedure siftUp(a, start, end) is     input:  start represents the limit of how far up the heap to sift end is the node to sift up.     child := end      while child > start         parent := floor((child-1)
2) if a[parent] < a[child] then (out of max-heap order) swap(a[parent], a[child]) child := parent (repeat to continue sifting up the parent now) else\ return


terima kasih semoga bermanfaat
source =  http://en.wikipedia.org/wiki/Heapsort