Yığın Sıralaması

Elde iki seçenek vardı: her durumda güvenceli ama $O(n)$ ek alan isteyen birleştirmeli sıralama, ya da yerinde çalışan ama en kötü durumu karesel olan hızlı sıralama. Üçüncü bir yol, her iki iyi özelliği birden verir.

Araç, Veri Yapıları kursunda tanıtılan ikili yığındır (binary heap).

Diziyle Yığın

Yığın, tam ikili bir ağaçtır ve tam olduğu için işaretçi olmadan bir dizide tutulabilir. i numaralı düğüm için:

• Sol çocuk: 2i + 1
• Sağ çocuk: 2i + 2
• Ebeveyn: (i - 1) // 2

Maksimum yığın koşulu, her düğümün çocuklarından küçük olmamasıdır. Kök, dizinin en büyük elemanıdır.

Koşul bozulduğunda düzelten işlem aşağı süzmedir: bir düğüm, çocuklarının büyüğüyle yer değiştirerek yerini bulana kadar iner.

def asagi_suz(d: list[int], kok: int, sinir: int) -> None:
    """d[kok] düğümünü, d[0..sinir) yığınında yerine indirir.

    Değişmez: kök dışındaki her düğüm yığın koşulunu sağlar.
    Sonlanma: kok her turda en az bir düzey artar.
    """
    while True:
        en_buyuk = kok
        sol, sag = 2 * kok + 1, 2 * kok + 2
        if sol < sinir and d[sol] > d[en_buyuk]:
            en_buyuk = sol
        if sag < sinir and d[sag] > d[en_buyuk]:
            en_buyuk = sag
        if en_buyuk == kok:
            return
        d[kok], d[en_buyuk] = d[en_buyuk], d[kok]
        kok = en_buyuk

Maliyet, düğümün inebileceği düzey sayısıyla sınırlıdır: $O(\log n)$.

Yığın Kurmak Doğrusaldır

Sırasız bir diziyi yığına çevirmenin yolu, yaprak olmayan düğümleri sondan başa doğru süzmektir. Yapraklar zaten geçerli birer yığındır, dolayısıyla işlem ortadan başlar.

def yigin_kur(d: list[int]) -> None:
    for i in range(len(d) // 2 - 1, -1, -1):
        asagi_suz(d, i, len(d))


ornek = [5, 2, 9, 1, 5, 6]
yigin_kur(ornek)
print(ornek)          # [9, 5, 6, 1, 2, 5]

Yüzeysel bakış $n$ düğümün her biri için $O(\log n)$ verip $O(n \log n)$ tahmin eder. Gerçek maliyet daha düşüktür, çünkü düğümlerin çoğu kısa yolları kat eder: yaprağa yakın düğümler çoğunluktadır ve az iner.

Yükseklik $h$ olan düğüm sayısı en çok $n / 2^{h+1}$’dir ve her biri en çok $h$ adım iner:

$$\sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot h \;\leq\; n \sum_{h=0}^{\infty} \frac{h}{2^{h+1}} = n$$

Toplam $O(n)$’dir — yığın kurmak, tek tek ekleme yapmaktan ($O(n \log n)$) ucuzdur.

def kurma_adimlari(d: list[int]) -> int:
    sayac = 0

    def suz(kok: int, sinir: int) -> None:
        nonlocal sayac
        while True:
            en_buyuk, sol, sag = kok, 2 * kok + 1, 2 * kok + 2
            if sol < sinir and d[sol] > d[en_buyuk]:
                en_buyuk = sol
            if sag < sinir and d[sag] > d[en_buyuk]:
                en_buyuk = sag
            if en_buyuk == kok:
                return
            d[kok], d[en_buyuk] = d[en_buyuk], d[kok]
            sayac += 1
            kok = en_buyuk

    for i in range(len(d) // 2 - 1, -1, -1):
        suz(i, len(d))
    return sayac


for n in (1_000, 10_000, 100_000):
    veri = [(i * 7919) % n for i in range(n)]
    print(n, kurma_adimlari(veri))

# 1000 706
# 10000 7529
# 100000 71808

Yer değiştirme sayısı $n$ ile doğru orantılı kalır — üç ölçümde de yaklaşık $0{,}72n$. $n \log_2 n$ olsaydı yüz bin eleman için bir buçuk milyonu aşardı.

Sıralama

Yığın kurulduktan sonra sıralama basittir: kök (en büyük) dizinin sonuna alınır, yığın sınırı bir küçültülür ve yeni kök süzülür.

def yigin_siralamasi(dizi: list[int]) -> list[int]:
    d = list(dizi)
    yigin_kur(d)
    for sinir in range(len(d) - 1, 0, -1):
        d[0], d[sinir] = d[sinir], d[0]     # en büyüğü yerine koy
        asagi_suz(d, 0, sinir)              # kalan bölümü onar
    return d


print(yigin_siralamasi([5, 2, 9, 1, 5, 6]))       # [1, 2, 5, 5, 6, 9]
print(yigin_siralamasi([3, 3, 3]))                # [3, 3, 3]
print(yigin_siralamasi([]))                       # []

Değişmez şudur: her turdan sonra dizinin sağ ucu kesin sıralıdır ve sol bölüm geçerli bir yığındır.

Maliyet: kurma $O(n)$, ardından $n-1$ kez $O(\log n)$ süzme; toplam $\Theta(n \log n)$ — her durumda. En kötü durum güvencesi vardır ve ek alan $O(1)$’dir; algoritma yerinde çalışır.

Kararlı değildir: kökle sondaki elemanın yer değiştirmesi, eşit anahtarlıların sırasını bozar.

Üç Algoritmanın Karşılaştırması

Ölçüt	Birleştirmeli	Hızlı	Yığın
En kötü durum	$\Theta(n \log n)$	$\Theta(n^2)$	$\Theta(n \log n)$
Ortalama	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n \log n)$
Ek alan	$O(n)$	$O(\log n)$ yığıt	$O(1)$
Kararlı	Evet	Hayır	Hayır
Bellek erişimi	Ardışık	Çoğunlukla yerel	Dağınık

Son satır, yığın sıralamasının neden en iyi güvencelere sahip olmasına karşın pratikte her zaman ilk tercih olmadığını açıklar. Süzme işlemi diziyi 2i + 1 sıçramalarıyla gezer; Bilgisayarlar Nasıl Çalışır kursundaki önbellek satırı mantığı burada aleyhe işler. Hızlı sıralamanın bölümlemesi ise diziyi baştan sona ardışık okur.

Bu gözlem, yaygın bir karma tasarımı doğurur: hızlı sıralamayla başlanır, özyineleme derinliği bir eşiği aşarsa (yani bölmeler dengesizleşiyorsa) yığın sıralamasına geçilir ve küçük parçalar eklemeli sıralamaya bırakılır. Sonuç, hızlı sıralamanın pratik hızını yığın sıralamasının en kötü durum güvencesiyle birleştirir.

İlk k Eleman

Yığının sıralama dışındaki asıl kullanımı öncelik kuyruğudur; bunun sıralamaya en yakın uygulaması, tüm veriyi sıralamadan en büyük $k$ elemanı bulmaktır.

Yöntem, $k$ boyutlu bir minimum yığın tutmaktır: yeni eleman yığının kökünden büyükse kök atılır, yenisi girer.

import heapq


def en_buyuk_k(veri: list[int], k: int) -> list[int]:
    """En büyük k elemanı artan sırada döndürür. Maliyet O(n log k)."""
    yigin: list[int] = []
    for deger in veri:
        if len(yigin) < k:
            heapq.heappush(yigin, deger)
        elif deger > yigin[0]:
            heapq.heapreplace(yigin, deger)
    return sorted(yigin)


veri = [(i * 7919) % 1000 for i in range(1000)]
print(en_buyuk_k(veri, 5))            # [995, 996, 997, 998, 999]
print(en_buyuk_k([5, 2, 9, 1, 5, 6], 3))     # [5, 6, 9]

Maliyet $O(n \log k)$’dir; $k$ küçükse bu, sıralamanın $O(n \log n)$’inden belirgin biçimde ucuzdur. Ek alan $O(k)$’dir — veri bir akıştan geliyor ve tamamı belleğe sığmıyorsa tek uygulanabilir yol budur.

Özet

• Tam ikili ağaç olan yığın, işaretçisiz biçimde bir dizide tutulur; çocuk ve ebeveyn dizinleri aritmetikle bulunur.
• Aşağı süzme $O(\log n)$’dir; yaprak olmayan düğümleri sondan başa süzerek yığın kurmak $O(n)$’dir.
• Yığın sıralaması kökü sona taşıyıp sınırı daraltır; her durumda $\Theta(n \log n)$ ve yerinde çalışır.
• Kararlı değildir ve belleğe dağınık eriştiği için sabiti hızlı sıralamadan büyüktür.
• Karma tasarımlar, hızlı sıralamanın hızını yığın sıralamasının güvencesiyle birleştirir.
• $k$ boyutlu yığın, en büyük $k$ elemanı $O(n \log k)$ maliyetle ve $O(k)$ alanla verir.

Sonraki Adım

Üç algoritma da doğrusal-logaritmik sınıra dayandı; bu bir rastlantı değil, karşılaştırmaya dayalı sıralamanın alt sınırıdır. Sonraki ders önce bu alt sınırı kanıtlayacak, sonra sınırın nasıl aşılabileceğini gösterecek: elemanları karşılaştırmayan, onları doğrudan konumlarına yerleştiren sıralamalar.