Heap sort

Heap sort adalah salah satu cara dari beberapa cara pengurutan yang ada.
Heap sort merupakan cara yang tercepat untuk mengurutkan angka, huruf, string, dan lain-lain.
Heap sort memiliki kompleksitas algoritma (O(n)) = n log n

Lebih lengkap :
Struktur data heap adalah array objek yang dapat dengan mudah divisualisasi sebagai sebuah complete binary tree. Terdapat sebuah one to one koresponden antara element - element array dan node -node tree. Tree diisi pada semua level kecuali mungkin ada yang terendah dimana diisi dari kiri sampai 'a point'. Semua node heap juga 'memuaskan' hubungan dimana nilai kunci pada setiap node setidaknya sama besar dengan nilai pada anaknya.

Langkah-langkahnya :
1. User menginput ukuran heap. Lalu program menghasilkan binary tree yang saling berkaitan
dengan node mempunyai nilai kunci yang dihasilkan secara acak.

2. Membangun operasi heap
Misalkan n adalah nomor node di dalam tree dan i adalah kunci sebuah tree. Untuk ini,
program menggunakan operasi heapify. Ketika heapify dipanggil keduanya subtree kiri dan
kanan i adalah heap. Fungsi heapify adalah meletakkan i ke sebuah posisi ( dengan
pertukaran dirinya dengan nilai yang lebih besar pada anaknya, sewaktu sifat heap tidak
terpenuhi ) sampai sifat heap terpenuhi di dalam tree dimana 'diakarkan' pada i. Operasi ini memanggil.

3. Hilangkan elemen maksimum
Program menghilangkan elemen terbesar pada heap ( root ) dengan menukarkannya dengan
elemen terakhir.

4. Program mengeksekusi heapify( root baru ) jadi menghasilkan tree yang memenuhi sifat heap

5. Ulangi langkah 3 sampai heap habis atau kosong.

Berikut disertakan contoh kodingan dengan menggunakan bahasa c.
http://download.gilaupload.com/filepointer.php?fid=deae6d6ca7abe9e3779f0263ae22cdd8

Untuk animasi :
http://www2.hawaii.edu/~copley/665/HSApplet.html