---
title: Yığınlar
source: 'https://academia.sh/tr/kurslar/veri-yapilari/yiginlar'
course: 'Veri Yapıları'
language: tr
updated: '2026-08-17T18:08:02+00:00'
license: 'CC BY-SA 4.0'
---

# Yığınlar

Öncelik kuyruğu, yığın koşulu, dizi gösterimi, yukarı ve aşağı süzme, yığın kurmanın doğrusal maliyeti.

Kuyruklar dersinde bir soru açıkta bırakılmıştı: elemanların geliş sırasının değil
**önem sırasının** belirleyici olduğu durumlarda ne yapılır? Bir işletim sistemi hangi
süreci çalıştıracağına, bir yönlendirme algoritması hangi düğümü genişleteceğine öncelik
bakarak karar verir.

**Öncelik kuyruğu (priority queue)**, bu soruya yanıt veren soyut veri tipidir: elemanlar
eklenir, çıkarıldığında **en öncelikli** olan gelir.

## Tam Sıralama Gerekmez

Öncelik kuyruğu sıralı bir yapıyla gerçeklenebilir — her eklemede sıraya sokulur, en
baştaki çıkarılır. Ancak bu, gereğinden fazla iş yapar: kuyruk yalnızca **bir sonraki**
elemanı bilmek zorundadır; geri kalanının tam sırası önemsizdir.

**Yığın (heap)**, tam sıralama ile hiç sıralamamak arasındaki dengeyi kurar. Koşulu
şudur:

> Her düğümün değeri, çocuklarının değerlerinden küçük veya eşittir (en küçük yığın).

Bu **kısmi** bir sıralamadır. Kardeşler arasında hiçbir ilişki yoktur; yalnızca ebeveyn–
çocuk ekseninde düzen korunur. Kökün en küçük eleman olması bu koşulun doğrudan sonucudur.

En büyük yığın, koşulun tersidir ve kökte en büyük elemanı tutar.

## Tam Ağaç ve Dizi Gösterimi

Yığın her zaman **tam ikili ağaçtır**: seviyeler soldan sağa doldurulur, boşluk yalnızca
son seviyenin sağ ucundadır. Bu biçim güvencesi, ikili ağaçlar dersindeki dizi
gösterimini uygulanabilir kılar:

$$
\text{sol}(i) = 2i+1, \qquad \text{sağ}(i) = 2i+2, \qquad \text{ebeveyn}(i) = \left\lfloor \tfrac{i-1}{2} \right\rfloor
$$

Yığının işaretçi tutmamasının iki sonucu vardır: bellek ek yükü yoktur ve elemanlar
bitişik durduğu için önbellek davranışı iyidir. Ağaç yapısı yalnızca kavramsaldır; veri
düz bir dizidir.

## İki Süzme İşlemi

Yığın koşulu, iki yerel onarım işlemiyle korunur.

**Yukarı süzme (sift-up)**, eklemede kullanılır. Yeni eleman dizinin sonuna — yani ağacın
son yaprağına — konur ve koşul sağlanana kadar ebeveyniyle yer değiştirerek yukarı
taşınır.

**Aşağı süzme (sift-down)**, çıkarmada kullanılır. Kök çıkarıldığında yerine son eleman
konur ve koşul sağlanana kadar küçük çocuğuyla yer değiştirerek aşağı iner.

Her iki işlem de kökten yaprağa giden bir yol boyunca ilerler; maliyetleri $O(\log n)$'dir.

```python
class Yigin:
    """En küçük yığın: kök her zaman en küçük elemandır."""

    def __init__(self) -> None:
        self._veri: list[int] = []

    def __len__(self) -> int:
        return len(self._veri)

    def ekle(self, deger: int) -> None:
        self._veri.append(deger)
        self._yukari_suz(len(self._veri) - 1)

    def en_kucuk(self) -> int:
        if not self._veri:
            raise IndexError("yığın boş")
        return self._veri[0]

    def cikar(self) -> int:
        if not self._veri:
            raise IndexError("yığın boş")
        en_kucuk = self._veri[0]
        son = self._veri.pop()
        if self._veri:
            self._veri[0] = son            # son eleman köke taşınır
            self._asagi_suz(0)
        return en_kucuk

    def _yukari_suz(self, i: int) -> None:
        while i > 0:
            ebeveyn = (i - 1) // 2
            if self._veri[i] >= self._veri[ebeveyn]:
                break                      # koşul sağlandı
            self._veri[i], self._veri[ebeveyn] = self._veri[ebeveyn], self._veri[i]
            i = ebeveyn

    def _asagi_suz(self, i: int) -> None:
        n = len(self._veri)
        while True:
            en_kucuk, sol, sag = i, 2 * i + 1, 2 * i + 2
            if sol < n and self._veri[sol] < self._veri[en_kucuk]:
                en_kucuk = sol
            if sag < n and self._veri[sag] < self._veri[en_kucuk]:
                en_kucuk = sag
            if en_kucuk == i:
                break
            self._veri[i], self._veri[en_kucuk] = self._veri[en_kucuk], self._veri[i]
            i = en_kucuk


y = Yigin()
for olcum in (25, 7, 30, 12, 18, 3):
    y.ekle(olcum)

print(y.en_kucuk(), len(y))        # 3 6
print([y.cikar() for _ in range(6)])   # [3, 7, 12, 18, 25, 30]
```

Elemanların çıkarma sırasında sıralı gelmesi, yığının sıralı olduğu anlamına gelmez:
dizinin kendisi hiçbir zaman tümüyle sıralı değildir. Sıralı çıktı, her çıkarmanın en
küçüğü seçmesinden doğar.

## Yığın Kurmanın Maliyeti

Elde bir dizi varsa ve tümü yığın hâline getirilecekse, her elemanı tek tek eklemek
$O(n \log n)$ sürer. Daha iyi bir yol vardır: dizideki **son iç düğümden** başlayarak
geriye doğru aşağı süzme uygulamak.

```python
def yigin_kur(veri: list[int]) -> Yigin:
    """Var olan diziyi yerinde yığına çevirir: O(n)."""
    y = Yigin()
    y._veri = list(veri)
    for i in range(len(veri) // 2 - 1, -1, -1):     # son iç düğümden köke
        y._asagi_suz(i)
    return y


y = yigin_kur([25, 7, 30, 12, 18, 3])
print(y.en_kucuk())                 # 3
print([y.cikar() for _ in range(6)])    # [3, 7, 12, 18, 25, 30]
```

Bu yöntemin maliyeti sezginin aksine $O(n \log n)$ değil, $O(n)$'dir. Gerekçesi düğüm
dağılımındadır: düğümlerin yarısı yapraktır ve hiç süzülmez; dörtte biri bir seviye,
sekizde biri iki seviye süzülür. Toplam, her düğümün en yüksek maliyeti ödediği
varsayımından belirgin biçimde küçük çıkar. Kesin çözümleme **Algoritmalar** kursuna
aittir.

## Kullanım Alanları

**Öncelikli zamanlama.** İşletim sistemi süreç seçimi, olay güdümlü simülasyonlarda bir
sonraki olayın seçilmesi.

**Çizge algoritmaları.** En kısa yol ve minimum kapsayan ağaç algoritmaları, sıradaki en
ucuz kenarı yığından çeker. Bu algoritmalar **Algoritmalar** kursunda ele alınır.

**En büyük k eleman.** Milyonlarca değer arasından en büyük yüzü bulmak için tümünü
sıralamak gerekmez: yüz elemanlık bir yığın tutulur, her yeni değer kökle karşılaştırılır.
Bellek $O(k)$, maliyet $O(n \log k)$ olur.

**Akan ortanca.** Programlama Temelleri kursunda tanıtılan iki yığın kalıbı: küçük yarıyı
en büyük yığında, büyük yarıyı en küçük yığında tutmak, ortancayı sabit zamanda verir.

**Sıralama.** Tüm elemanları yığına koyup tek tek çıkarmak $O(n \log n)$ bir sıralama
algoritmasıdır; yığın sıralaması olarak bilinir.

Bir ayrıntı, öncelik kuyruğu kullanan algoritmalarda önem kazanır: yığında bulunan bir
elemanın önceliği sonradan değişirse, yapı kendiliğinden düzelmez. Bu durum için ya
öncelik güncelleme işlemi ayrıca gerçeklenir ya da eski kayıt geçersiz sayılıp yenisi
eklenir; ikinci yol daha basittir ve yığında geçersiz kayıtlar biriktirir.

## Maliyet Tablosu

| İşlem | Yığın | Sıralı dizi | Sırasız dizi |
|---|---|---|---|
| En küçüğü görme | $O(1)$ | $O(1)$ | $O(n)$ |
| Ekleme | $O(\log n)$ | $O(n)$ | $O(1)$ |
| En küçüğü çıkarma | $O(\log n)$ | $O(1)$* | $O(n)$ |
| Yığın kurma | $O(n)$ | $O(n \log n)$ | $O(1)$ |
| Arama (rastgele eleman) | $O(n)$ | $O(\log n)$ | $O(n)$ |

\* Baştan silme kaydırma gerektiriyorsa $O(n)$.

Son satır, yığının sınırıdır: kök dışındaki bir elemanı aramak için tüm yapı gezilir.
Yığın, sıralama için değil **uç elemana erişim** için tasarlanmıştır.

## Özet

- Öncelik kuyruğu, çıkarıldığında en öncelikli elemanı veren soyut tiptir.
- Yığın koşulu kısmi bir sıralamadır: ebeveyn çocuklarından küçüktür, kardeşler arasında
  ilişki yoktur.
- Yığın her zaman tam ikili ağaçtır ve diziyle gösterilir; işaretçi ek yükü yoktur.
- Ekleme yukarı süzme, çıkarma aşağı süzme ile koşulu onarır; ikisi de logaritmiktir.
- Var olan bir diziden yığın kurmak, tek tek eklemekten ucuzdur ve doğrusal zamanlıdır.
- Yığın, uç elemana erişim için tasarlanmıştır; rastgele eleman araması doğrusaldır.

## Sonraki Adım

Buraya kadarki arama yapıları anahtarları bütün olarak karşılaştırdı. Anahtarlar dizgi
olduğunda farklı bir olanak doğar: ortak önekler bir kez saklanabilir ve karşılaştırma
karakter karakter yapılabilir. Sonraki ders bu fikri kuran sözcük ağaçlarını ele alacak.