Yığınlar

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.

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.

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.