Heapsort (yığın sıralaması)

Kısaca: Heapsort, verileri bir max-yığına (max-heap) dönüştürüp ardından en büyük öğeyi tekrar tekrar sona taşıyarak sıralar.

Biraz daha ayrıntılı: En kötü durumda bile her zaman O(n log n)‘de çalışır ve ek bellek gerektirmez. Ancak pratikte genellikle quicksort’tan yavaştır; çünkü belleği doğrusal değil sıçramalı okur.

Ayrıntılı

• 1. adım: Dizi O(n)‘de bir max-yığına dönüştürülür: ortadan geriye doğru her düğüm aşağıya “batırılır”.
• 2. adım: Kök (en büyük öğe) son öğeyle yer değiştirir. Yığın 1 küçülür ve yeni kök batırılır.
• Yinele, yığın boşalana dek. Dizi o zaman artan sıralıdır.
• Özellikler: kararlı değil, yerinde (in place), ön sıralılıktan bağımsız.
• Kullanım: Quicksort çok derine özyinelerse introsort’ta yedek olarak. Bkz. yığın ve öncelik kuyruğu.

Ayrıca bak: Birleştirme sıralaması