---
title: 'Yığın Sıralaması'
source: 'https://academia.sh/tr/kurslar/algoritmalar/yigin-siralamasi'
course: Algoritmalar
language: tr
updated: '2026-08-17T18:07:42+00:00'
license: 'CC BY-SA 4.0'
---

# Yığın Sıralaması

Dizi üzerinde ikili yığın, aşağı süzme, doğrusal maliyetli yığın kurma, yerinde ve garantili doğrusal-logaritmik sıralama, ilk k eleman.

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.

```python
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.

```python
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.

```python
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.

```python
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.

```python
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.