Yığın Sıralaması (Heap Sort)

#Nasıl çalışır?

Yığın sıralaması (heap sort), diziyi önce bir max-heap'e dönüştürür: her ebeveyn çocuklarından büyük olur, bu yüzden en büyük eleman kökte, yani dizinin başında durur.

Ardından kökteki en büyük eleman dizinin sonuna gönderilir ve kalan kısımda heap kuralı yeniden sağlanır. Bu işlem her seferinde bir eleman kesin yerine oturana kadar tekrarlanır.

Ek bellek kullanmaz ve en kötü durumda bile O(n log n) çalışır. Bu iki özelliği birlikte sunan az sayıdaki sıralama algoritmasından biridir.

#Canlı animasyon

for i = n/2 - 1 down to 0: siftDown(i, n)   // build a max-heap
for end = n - 1 down to 1:
  swap(a[0], a[end])   // the maximum goes to its final place
  siftDown(0, end)
siftDown(i, size): swap a[i] with its larger child while that child is larger

#Adım adım

1. 01Diziyi max-heap'e dönüştür: son ebeveynden başlayıp köke kadar her düğümü aşağı indir (sift down).
2. 02Kökteki en büyük elemanı dizinin son elemanıyla yer değiştir.
3. 03O eleman artık kesin yerinde; heap'i bir küçült.
4. 04Yeni kökü aşağı indirerek heap kuralını yeniden sağla.
5. 05Heap'te tek eleman kalana kadar tekrarla.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def sift_down(a: list[int], i: int, size: int) -> None:
    """Moves a[i] down until both children are smaller (max-heap of a[:size])."""
    while True:
        left, right, largest = 2 * i + 1, 2 * i + 2, i
        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest


def heap_sort(a: list[int]) -> None:
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):  # build a max-heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]  # the maximum goes to its final place
        sift_down(a, 0, end)


numbers = [5, 1, 4, 2, 8, 3]
heap_sort(numbers)
print(*numbers)

#Karmaşıklık

Heap'i kurmak O(n), her çıkarma O(log n) sürer; n çıkarma ile toplam O(n log n). Bu süre verinin sırasına bağlı değildir. Pratikte quick sort'tan biraz yavaştır, çünkü bellekte uzak elemanlarla çalışır ve önbelleği daha az verimli kullanır.

#Ne zaman kullanılır?

Ek bellek kullanmadan O(n log n) garantisi gerektiğinde idealdir; gömülü sistemler ve gerçek zamanlı sistemler buna örnektir. Introsort (C++ std::sort) quick sort çok derine indiğinde heap sort'a geçer. "En büyük k eleman" gibi kısmi sıralamalarda da heap fikri kullanılır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.