Öncelik Kuyrukları

OYUNLARDA YAPAY ZEKÂ · ÖNCELİK KUYRUKLARI

Öncelik Kuyrukları

İkili yığın, heapsort, zamanlayıcılar — “en önemli olan önce”

PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

API ve basit uygulamalar — sırasız ve sıralı dizi
İkili yığın — tam ikili ağaç, dizi içinde! binary heap
swim — eklenen eleman yukarı yüzer
sink — kök çıkarılınca yenisi aşağı batar
Heapsort — yerinde, en kötü durumda bile N lg N
Oyunda — zamanlayıcılar, en iyi k skor, olay güdümlü simülasyon, A*’a hazırlık

🎮 Bu dersin sonunda…

…“3,2 saniye sonra patla”, “5 saniye sonra kalkanı kapat” gibi binlerce zamanlayıcıyı her karede tek tek kontrol etmeden yönetebilecek ve yol bulma algoritması A*’ın kalbindeki veri yapısını tanıyor olacaksınız.

🤔 ISINMA: ACİL SERVİS

Hastanede acil servise sırayla hastalar geliyor. Doktor boşalınca kimi çağırmalı?

Yığın stack: en son geleni → olmaz 😬
Kuyruk queue: ilk geleni → adil ama kalp krizi beklerken parmak kesiği muayene ediliyor 😬
Öncelik kuyruğu priority queue: en acil olanı! Ve sürekli yeni hastalar geliyor.

🎮 Kule savunması: “hangi düşmana ateş edeyim?” → en tehlikeli · RTS: “hangi işi önce yapayım?” · Zamanlayıcı: “hangi olayın zamanı ilk gelecek?”

Mini sözlük

priority queue (PQ)	öncelik kuyruğu	En büyük (ya da en küçük) anahtarı hızla çıkaran yapı
insert · delMax · delMin	ekle · en büyüğü / küçüğü çıkar	PQ’nun iki temel işlemi
complete binary tree	tam ikili ağaç	Son seviye hariç dolu; son seviye soldan sağa dolar
binary heap	ikili yığın	Diziye yerleştirilmiş, yığın düzenli tam ikili ağaç
heap order	yığın düzeni	Her ebeveyn çocuklarından büyük-eşit
swim · sink	yüzdürme · batırma	Diğer adları: sift up · sift down, bubble up · down
heapify · heapsort	yığın kurma · yığın sıralaması	Diziyi yerinde yığına çevirme · yığınla sıralama
event-driven simulation	olay güdümlü benzetim	Zamanı karelerle değil, olaydan olaya atlayarak ilerletmek

⚠️ “Yığın” kelimesi Türkçede iki şey için kullanılıyor: stack (Yığınlar ve Kuyruklar sunumu) ve heap (bu sunum). Bellekteki “heap” (GC’nin yönettiği alan) ise üçüncü, ilgisiz bir anlam! Karışmasın diye İngilizcesini de söyleyeceğiz.

LEVEL 0

API ve basit uygulamalar

ne istiyoruz, ilk akla gelen yollar ne kadar iyi?

API ve basit uygulamalar
ikili yığın
swim: ekleme
sink: en büyüğü çıkarma
heapsort
oyunda öncelik kuyrukları

Öncelik kuyruğu API’si

MaxPQ()	boş öncelik kuyruğu oluştur
insert(v)	v anahtarını ekle
delMax()	en büyük anahtarı çıkar ve döndür
max()	en büyüğü döndür (çıkarmadan)
isEmpty() · size()	boş mu? · kaç eleman?

MinPQAynısının ayna görüntüsü: delMin(), min(). Zamanlayıcılarda ve yol bulmada MinPQ kullanılır (“en erken zaman”, “en kısa yol”).

🎮 Anahtar = öncelikKule savunması: anahtar = düşmanın çıkışa yakınlığı. Zamanlayıcı: anahtar = olay zamanı. Skor tablosu: anahtar = skor.

Örnek istemci: en iyi M skor

1 milyar maç oynandı (N). En yüksek M = 10 skoru bul. Hepsini belleğe sığdıramıyoruz bile!

yöntem	süre	bellek
hepsini sırala	N lg N	N
basit PQ (dizi)	N M	M
ikili yığın	N lg M	M

FikirM elemanlı bir MIN-yığın tut. Yeni skor, yığının en küçüğünden büyükse: en küçüğü at, yeniyi ekle. Yığında her an “şimdiye kadarki en iyi M” var. (Birazdan canlı göreceğiz!)

İlk akla gelen iki uygulama

Sırasız dizi unordered array

insert: sona ekle → 1
delMax: hepsine bakıp en büyüğü bul → N

Tembel: işi son ana bırakır.

Sıralı dizi ordered array

insert: doğru yere yerleştir (kaydır) → N
delMax: sondakini al → 1

Hevesli: işi hemen yapar.

uygulama	insert	delMax	max
sırasız dizi	1	N	N
sıralı dizi	N	1	1
hedef	lg N	lg N	1

🔗 Başka gözle: etkileşimli anlatımlar ve yazılar

Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.

📊 İkili yığın (binary heap)

VisuAlgo (NUS)

Ekleme ve en büyüğü çıkarmada elemanın nasıl yukarı ve aşağı yüzdüğünü, ağaç ve dizi görünümü yan yana gösterir.

📘 Event Queue

Game Programming Patterns (Robert Nystrom)

Oyunlarda olay kuyruğu: dairesel tamponla ses ve olay yönetimi.

🔗 Data Structure Visualizations

David Galles (USF)

Neredeyse her veri yapısı için bir oyun alanı: ekle, sil, ara düğmeleriyle yapının nasıl değiştiğini izleyin.

Ölçüm: N ekle + N çıkar

Basit uygulamalar ~N² (N 4 katına çıkınca süre ~16 katı). İkili yığın N lg N: 1 milyon eleman bile göz açıp kapayıncaya kadar.

Quiz 1 · API

Bir RTS’de saniyede 100 yeni iş ekleniyor ve 100 iş çıkarılıyor. Sıralı dizi ile yapılan öncelik kuyruğunda 10.000 iş varken bir insert en kötü durumda kaç eleman kaydırır?

Sıralı dizide yeni eleman en başa gidecekse, arkasındaki herkes bir sağa kaymalı: ~N = 10.000 kaydırma. İkili yığında ekleme en fazla ~lg N = 14 karşılaştırma.

LEVEL 1

İkili yığın

binary heap — dizi içinde yaşayan bir ağaç

API ve basit uygulamalar
ikili yığın
swim: ekleme
sink: en büyüğü çıkarma
heapsort
oyunda öncelik kuyrukları

Tam ikili ağaç complete binary tree

Son seviye hariç bütün seviyeler dolu
Son seviye soldan sağa dolar
N düğümlü tam ikili ağacın yüksekliği: ⌊lg N⌋. (Seviye her inişte 2 katına çıkar.) N = 1 milyon → yükseklik 19
Şekli sadece N’ye bağlı! Ekleme sırası şekli değiştirmez (BST’nin aksine)

11 düğümlü tam ikili ağaç: son seviyede soldan 4 yer dolu.

Yığın düzeni ve dizi temsili

Yığın düzeni heap orderHer düğüm çocuklarından büyük ya da eşit. → En büyük anahtar kökte: a[1].

Dizi hâliDüğümleri seviye seviye, soldan sağa diziye yaz. Hiç bağlantı (işaretçi) yok! k’nın çocukları 2k ve 2k+1, ebeveyni k/2.

🎒 Ön bilgi: 1’den başlayan indeks ve tam sayı bölmesi

a[0]’ı boş bırakıyoruz: yığın a[1]’den başlar. Böylece formüller çok sade olur.
Tam sayı bölmesi integer division: 5 / 2 = 2 (kalan atılır)
- Python: k // 2 (tek / ondalık verir: 2.5!)
- C#: k / 2 (int / int → int)
- JavaScript: Math.floor(k / 2) ya da k >> 1 (bit kaydırma: “ikiye böl”)

k	ebeveyn k/2	sol 2k	sağ 2k+1
1 (kök)	—	2	3
2	1	4	5
5	2	10	11
6	3	12	13
11	5	22	23

0’dan başlasaydık: çocuklar 2k+1, 2k+2, ebeveyn (k−1)/2. Çalışır ama formüller daha karışık. Heapsort kodunda bu sürümü de göreceğiz.

⚙️ Neden dizi? Düşük seviye kazançlar

İşaretçi yok: BST düğümünde anahtar + 2 bağlantı (64 bitte 16 bayt fazladan). Yığında sadece anahtar.
Önbellek dostu: üst seviyeler dizinin başında, birbirine yakın → sık kullanılan kısım önbellekte kalır.
Çöp toplayıcı dostu: tek bir dizi; binlerce küçük düğüm nesnesi yok → çöp toplayıcıya iş yok, oyunda takılma yok. 📖 Çöp toplayıcı (garbage collector, kısaca GC): C#, Java, JavaScript ve Python’da artık kullanılmayan nesneleri bellekten kendiliğinden silen mekanizma. Silme işi arada bir topluca yapılır ve o an oyun birkaç milisaniye durabilir; bu yüzden oyun kodunda “her karede yeni nesne üretme” kuralı vardır.
Çocuk bulma = çarpma: 2k işlemcide bir bit kaydırma kadar ucuz.

Quiz 2 · ikili yığın

1’den başlayan bir ikili yığında a[9]’un ebeveyni ve çocukları hangi indekslerde?

Ebeveyn = 9 / 2 = 4 (tam sayı bölmesi, kalan atılır). Çocuklar 2·9 = 18 ve 2·9+1 = 19. B şıkkı Python’da / kullanınca yapılan klasik hata: indeks ondalık olamaz → // kullanın.

LEVEL 2

swim: ekleme

yeni eleman sona eklenir, ebeveyninden büyük oldukça yukarı yüzer

API ve basit uygulamalar
ikili yığın
swim: ekleme
sink: en büyüğü çıkarma
heapsort
oyunda öncelik kuyrukları

Yukarı yüzdürme swim · sift up

Bir düğüm ebeveyninden büyük oldu (yığın düzeni bozuldu):

Ebeveyniyle yer değiştir
Hâlâ yeni ebeveyninden büyükse tekrarla
Kökte ya da ebeveyninden küçükse dur

😄 Akılda tutmak için: şirkette terfiYığını bir şirket şeması gibi düşünün: her düğümün üstünde bir “müdürü” (ebeveyni) var. Yeni gelen en alta girer; müdüründen daha iyiyse onunla yer değiştirir (terfi) ve bunu, kendisinden iyi bir müdüre rastlayana kadar sürdürür. Yönetim bilimindeki ünlü şaka da bunu söyler: “Herkes, yetersiz kalacağı seviyeye kadar terfi eder” (Laurence J. Peter, 1969: “Peter ilkesi”). Düğümümüz de tam o noktada durur.

insert = sona ekle + swim. En fazla 1 + lg N karşılaştırma.

Ekleme — kendiniz deneyin

S’yi ekleyin: önce en sona (a[12]) gelir, sonra ebeveynleriyle karşılaştırılarak yukarı yüzer. Hem ağaçta hem dizide izleyin. Sonra Z, sonra B deneyin.

🧪 Kod laboratuvarı: swim yaz

Test: rastgele sayıları senin swim’inle tek tek yığına ekleyip sonra hepsini sırayla çıkarıyoruz; büyükten küçüğe çıkmalılar. Sonra k > 1 koşulunu silip ne olduğunu görün (ipucu: a[0]).

LEVEL 3

sink: en büyüğü çıkarma

kök son elemanla yer değiştirir, yeni kök aşağı batar

API ve basit uygulamalar
ikili yığın
swim: ekleme
sink: en büyüğü çıkarma
heapsort
oyunda öncelik kuyrukları

Aşağı batırma sink · sift down

Bir düğüm çocuklarından küçük oldu:

Çocuklarından büyük olanı seç
Onunla yer değiştir
Çocukları ondan küçükse ya da yaprağa geldiyse dur

😄 Güç savaşı“Patron yetersiz kaldı: astlarından daha iyi olanı onun yerine terfi eder, patron bir kademe düşer.”

delMax = kökü sakla + son elemanı köke koy + sink. En fazla 2 lg N karşılaştırma (her seviyede 2: iki çocuğu kıyasla, büyüğü ebeveynle kıyasla).

İkili yığın — oyun alanı

Hazır diziyi oynatın (* = delMax): ekleme yukarı yüzdürür, çıkarma aşağı batırır. Mor kesikli = karşılaştırılan çocuklar. ◀ Geri / İleri ▶ ile adım adım gidin.

🎒 Yığın kodundaki yeni ifadeler

a[k], a[j] = a[j], a[k]	takas swap (Python)	Sağ taraf önce değerlendirilir, sonra aynı anda atanır. C#: `(a[k], a[j]) = (a[j], a[k]);` (tuple) · JS: `[a[k], a[j]] = [a[j], a[k]];` (dizi ayrıştırma)
j < n and a[j] < a[j+1]	kısa devre + sınır	Önce `j < n`: sağ çocuk var mı? Yoksa `a[j+1]`’e hiç bakılmaz → dizi dışına çıkma hatası olmaz
while 2 * k <= n	“çocuğu var mı?”	Sol çocuk 2k; n’den büyükse k bir yaprak
a.pop() · RemoveAt · pop()	sondan silme	Dizinin sonundan silmek O(1): kaydırma yok

Takasın geleneksel (üç adımlı) hâli:

Sonuç: lg N garantisi

ÖnermeN anahtarlı ikili yığında insert en fazla 1 + lg N, delMax en fazla 2 lg N karşılaştırma yapar.

Çünkü tam ikili ağacın yüksekliği ⌊lg N⌋ ve her iki işlem tek bir kök–yaprak yolu boyunca ilerler.

uygulama	insert	delMax	max
sırasız dizi	1	N	N
sıralı dizi	N	1	1
ikili yığın	lg N	lg N	1
d-li yığın	log_d N	d log_d N	1
Fibonacci yığını	1	lg N *	1

* amortize (ortalama). Fibonacci yığını teoride çok iyi ama pratikte karmaşık ve yavaş; oyunlarda ikili (ya da 4-lü) yığın kullanılır. C#’ın PriorityQueue’su 4-lü bir yığındır: daha sığ ağaç, daha az önbellek ıskası.

🎬 Ara: ikili yığın nedir?

What Is a Binary Heap?
Spanning Tree · 8 dk 45 sn · YouTube’da aç

Yığının ağaç ve dizi hâli, yukarı çıkma (swim) ve aşağı inme (sink), çok temiz animasyonlarla. Bu bölümün demolarının iyi bir tekrarı.

🤔 İzlerkenVideoda dizideki i’nci elemanın çocukları hangi indekslerde? (Bizim 1’den başlayan indeksimizle karşılaştırın.) Kökü çıkarınca neden son eleman köke taşınıyor?

Quiz 3 · sink

Max-yığında delMax sırasında yeni kök iki çocuğuyla karşılaştırılıyor. Neden büyük çocukla yer değiştiriyoruz?

Yukarı çıkan çocuk, diğer çocuğun da ebeveyni olur. Ebeveyn çocuklarından büyük-eşit olmalı → yukarı ancak ikisinin büyüğü çıkabilir. C yanlış: yığında kardeşler arasında bir sıra yok.

LEVEL 4

Heapsort

yerinde ve en kötü durumda bile N lg N

API ve basit uygulamalar
ikili yığın
swim: ekleme
sink: en büyüğü çıkarma
heapsort
oyunda öncelik kuyrukları

Heapsort: iki aşama

1) Yığın kurma heap constructionDiziyi yerinde max-yığına çevir. Akıllı yol: sağdan sola, yaprak olmayan her düğümü batır (k = N/2 … 1). Yapraklar zaten 1 elemanlı yığın!

Toplam en fazla 2N karşılaştırma — N kez insert’ten (N lg N) daha iyi.

2) Sıralama sortdownKök (en büyük) ile son elemanı takasla → en büyük son yerinde. Yığını 1 küçült, kökü batır. Tekrarla.

delMax gibi; ama çıkan eleman, yığının boşalttığı yere yazılıyor. Ek dizi yok!

Heapsort — adım adım

“Yığın kur” sadece 1. aşamayı, “Heapsort” iki aşamayı birlikte oynatır. Dizide yeşil hücreler son yerine oturmuş elemanlar; ağaçta sadece yığında kalanlar görünür.

Heapsort — kod (0’dan başlayan indeksle)

🎒 range(n // 2 - 1, -1, -1): (başla, dur, adım) → n/2−1’den başla, −1’e gelmeden dur, birer birer azal. Geleneksel hâli: k = n // 2 - 1 · while k >= 0: … k -= 1

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`2 * k + 1`	k’nin sol çocuğu (0 tabanlı)	1 tabanlıda 2k idi; dizinin başından bir kaydık
`if (j + 1 < n && a[j] < a[j + 1]) j++`	iki çocuğun büyüğünü seç	ebeveyn büyük çocuktan küçükse onunla yer değiştirir
kurma döngüsü `n / 2 − 1`’den geriye	yaprak olmayan her düğümü batır	yapraklar zaten tek başına yığın; kurma ~2N karşılaştırma
`[a[0], a[n]] = [a[n], a[0]]`	en büyüğü (kökü) sona taşı	sondaki bölge sıralı büyür
`sink(a, 0, n)`	yığını bir kısalt ve kökü onar	toplam ~2N lg N karşılaştırma, ek bellek yok

Çubuklarla heapsort

Önce yığın kurma: dizi “testere dişi” gibi görünür (büyükler başta). Sonra en büyük çubuklar tek tek sona gider.

Yarış: mergesort vs quicksort vs heapsort

Karşılaştırma ve dizi erişimi sayaçlarına bakın. Heapsort’un erişimleri dizinin bir başına bir sonuna “zıplıyor”: önbellek için kötü haber.

Heapsort neden her yerde değil?

ÖnermeHeapsort yerinde çalışır ve en kötü durumda en fazla 2 N lg N karşılaştırma yapar.

Mergesort: N lg N ama ek N bellek. Quicksort: yerinde ama en kötü N². Heapsort ikisinin de zayıflığından kurtulan tek klasik algoritma!

⚠️ Ama pratikte…

Önbellek düşmanı: k → 2k atlamaları dizide uzak yerlere gider
İç döngüsü quicksort’unkinden uzun
Kararlı değil

Bu yüzden C#’ın Array.Sort’u ve C++’ın std::sort’u introsort kullanır: quicksort ile başla, özyineleme çok derinleşirse heapsort’a geç (Quicksort sunumu). Heapsort = sigorta poliçesi.

Sıralama karnesi

algoritma	yerinde?	kararlı?	en kötü	ortalama	en iyi	not
selection	✔		N²/2	N²/2	N²/2	N takas
insertion	✔	✔	N²/2	N²/4	N	küçük ya da neredeyse sıralı N
shell	✔		?	?	N	kısa kod, alt kuadratik
merge		✔	N lg N	N lg N	½ N lg N	garanti + kararlı
quick	✔		N²/2	1,39 N lg N	N lg N	pratikte en hızlı
3 yollu quick	✔		N²/2	1,39 N lg N	N	tekrar eden anahtarlar
heap	✔		2 N lg N	2 N lg N	N lg N	garanti + yerinde

Hepsini bu derste animasyonlarıyla gördünüz! 🏆

Quiz 4 · heapsort

Heapsort’un yığın kurma aşamasında neden k = N/2’den başlayıp geriye doğru gidiyoruz?

2k > N olan her k’nın çocuğu yok → yaprak. Yapraklar kendi başlarına geçerli bir yığın. Sağdan sola giderek her düğümü batırdığımızda, altındaki iki alt ağaç zaten yığın olmuş oluyor; sink bu ikisini birleştirir.

🐍 Kod laboratuvarı: sink düzelt (Python)

Test: senin sink’inle önce yığın kuruyoruz, sonra heapsort yapıyoruz. Bu kod bazı testlerde yanlış sonuç veriyor. Hangi satır eksik? (İpucu: iki çocuktan hangisiyle karşılaştırmalı?) Bonus: k = j satırını silin — ne oluyor?

LEVEL 5

Oyunda öncelik kuyrukları

zamanlayıcılar, en iyi k, olay güdümlü benzetim, A*

API ve basit uygulamalar
ikili yığın
swim: ekleme
sink: en büyüğü çıkarma
heapsort
oyunda öncelik kuyrukları

Problem: “3 saniye sonra patlat” diyen binlerce olay

🎮 Zamanlanmış olaylar

Bomba 3 saniye sonra patlayacak. Zehir her saniye can götürecek. Kalkan 8 saniye sonra bitecek. Düşman 20 saniye sonra yeniden doğacak.
Büyük bir oyunda aynı anda binlerce böyle bekleyen olay olur.

İlk akla gelen: hepsini bir listede tut; her karede listenin tamamını gez: “zamanı geldi mi?” 5.000 olay × saniyede 60 kare = saniyede 300.000 boş kontrol.
Gözlem: şu an tek bir olay önemli: en erken gerçekleşecek olan. Onun zamanı gelmediyse hiçbirininki gelmemiştir.
Çözüm: olayları, anahtarı gerçekleşme zamanı olan bir MIN-yığında tut. En erken olay hep kökte: her karede tek bir karşılaştırma.
Zamanı gelince kökü çıkar (delMin, lg N adım), olayı gerçekleştir, yeni köke bak.

Elle izleme: şimdi t = 0

olay	zamanı
🔥 yanma hasarı	0,6
🛡️ kalkan biter	5,7
💣 bomba patlar	13,5
👾 düşman doğar	6,9

Yığının kökü: 🔥 0,6 (en küçük zaman).
t = 0,3: kök 0,6 > 0,3 → hiçbir şey yapma. Öbür üç olaya bakılmadı.
t = 0,6: kökün zamanı geldi → çıkar, yanma hasarını uygula. Yeni kök: 🛡️ 5,7.
Yanma tekrarlanıyorsa: aynı olayı 1,6’ya yeniden ekle (insert).

Ağacın biçimi “kim kimden sonra” demek değildir; tek garanti şudur: her düğümün zamanı, altındakilerden küçüktür. Bu yüzden en erken olay kökte durur; gerisi yarı sıralıdır.

🎮 Olay zamanlayıcısı timer / scheduler

Üstte zaman çizgisi: her simge bekleyen bir olay, kırmızı çizgi “şimdi”. Altta aynı olayların yığını: düğümün solundaki simge olay, içindeki sayı zamanı. ⏭ Sıradaki olay: saat köke atlar, kök çıkarılır, yığın kendini onarır. ➕ Rastgele olay ekle: yeni olay en alta girip yerine yüzer.

🔗 Ayrıntısı: Y18 · YZ Performansı (olay tabanlı güncelleme) sunumunda.

Zamanlayıcı — kod

🎒 Ön bilgi: (öncelik, eleman) çiftleri

Python’da demet tuple (3.2, "bomba") karşılaştırılırken önce ilk elemana bakılır; eşitse ikinciye. Bu yüzden önceliği başa koyarız.
⚠️ İki olayın zamanı eşitse Python ikinci elemanları karşılaştırmaya çalışır. Olaylar nesneyse hata! Çözüm: araya bir sayaç koy: (zaman, sayaç, olay)
heapq sadece MIN-yığın. Max gerekiyorsa önceliği eksi yap: (-skor, oyuncu)
timers[0] = kök = en küçük (çıkarmadan bakmak: peek)

⚙️ Hangi dilde ne var?

Python: heapq (min; liste üzerinde fonksiyonlar)
C#: PriorityQueue<T,P> (.NET 6+, 4-lü min-yığın). Unity’nin .NET sürümünde bulunmayabilir → kendi yığınınızı yazın
C++: std::priority_queue (varsayılan max)
Java: PriorityQueue (min)
JavaScript: yok — kendiniz yazarsınız

🏆 Skorlar tek tek geliyor: en iyi 5’i nasıl tutarız?

Çevrimiçi bir oyunda skorlar bitmeyen bir sıra hâlinde gelir (buna veri akışı denir: hepsini saklayamazsınız, her birini bir kez görürsünüz). Liderlik tablosu için yalnızca en iyi 5 lazım. Numara: 5 elemanlı bir MIN-yığın tutmak. Kökü “en iyi 5’in en kötüsü”dür, yani giriş barajı: yeni skor barajı geçemiyorsa hemen atılır; geçiyorsa kök çıkar, yeni skor girer.

Olay güdümlü benzetim event-driven simulation

Bilardo topları (ya da gaz molekülleri) çarpışıyor:

Zaman güdümlü: her karede (dt) her çift için “çarpıştı mı?” → N² iş / kare. dt büyükse hızlı toplar birbirinin içinden geçer (tünelleme), küçükse çok yavaş.
Olay güdümlü: her çift ve her duvar için gelecekteki çarpışma zamanını hesapla, MinPQ’ya koy. Zamanı doğrudan sıradaki çarpışmaya atla!
Çarpışan toplar için yeni tahminler eklenir; artık geçersiz olan eski tahminler çıkarılınca atlanır.

📜 Olay güdümlü simülasyonÇarpışan parçacıklar: binlerce parçacık, MinPQ ile. Fizikte Boltzmann dağılımını bilgisayarda görmek için kullanılır.

🎮 OyundaBilardo/golf oyunlarının fiziği, sıra tabanlı stratejide “inisiyatif” sırası, RTS sunucusunda gelecekteki olaylar… Hepsinde “bir sonraki ne zaman?” sorusu → MinPQ.

🎮 Gelecek bölüm için kanca: A* yol bulma

Oyunlardaki yol bulmanın kralı A* algoritması bir açık liste open list tutar: “keşfedilmeyi bekleyen kareler”. Her adımda en umut verici kareyi (tahmini toplam maliyeti en küçük) seçer.

“En küçüğü seç, yenilerini ekle, tekrar et” → bu tam olarak bir MinPQ! Açık listeyi sıradan bir listeyle tutan bir A* büyük haritada saniyeler sürer; ikili yığınla milisaniyeler.

Önce “En Kısa Yollar” sunumunda Dijkstra’yı (A*’ın atası) MinPQ ile göreceğiz; A*’ın kendisi Oyun Yapay Zekâsı bölümünde.

Quiz 5 · oyunda

Bir oyunda 50.000 zamanlanmış olay var. Her karede “zamanı gelen olay var mı?” sorusu MIN-yığınla kaç karşılaştırma gerektirir (zamanı gelen yoksa)?

Sadece köke bakmak yeter: min() = a[1]. Kökteki olayın zamanı gelmediyse, ondan sonraki hiçbirinin zamanı gelmemiştir. Olay çıkarmak ise lg N ≈ 16 karşılaştırma. Sırasız bir listede her karede 50.000 olaya bakmak gerekirdi!

Derin hikâye: Linux çekirdeği neden heapsort kullanır?

Linux çekirdeğinin genel amaçlı sıralama fonksiyonu (lib/sort.c) quicksort değil, heapsorttur. Kaynak kodundaki açıklama: “Linux çekirdeği için hızlı, küçük, özyinelemesiz bir O(n log n) sıralama.”
Sebep 1: Çekirdeğin çağrı yığını çok küçüktür (birkaç kilobayt); derin özyineleme sistemi çökertebilir. (Çağrı yığını: her fonksiyon çağrısının yerel değişkenlerini tuttuğu bellek bölgesi; Yığınlar ve Kuyruklar sunumundaki “call stack”. Bu sunumdaki yığın veri yapısıyla (heap) yalnızca Türkçe adı aynı.) Heapsort sabit ek bellekle çalışır.
Sebep 2: Quicksort’un en kötü durumu O(n²); çekirdekte öngörülemeyen gecikme kabul edilemez. Heapsort’un en kötü durumu da O(n log n).
2019’da yapılan iyileştirmeyle (“aşağıdan yukarı” heapsort) karşılaştırma sayısı daha da azaltıldı.

DersOrtalama hız her şey değildir: garanti (en kötü durum) ve bellek bazen daha önemlidir. Oyunlarda da öyle: bir karede 50 ms takılma, ortalamada kazanılan milisaniyelerden pahalıdır. Yığın veri yapısının asıl gücü ise sıralamadan çok öncelik kuyruğu: A*’ın açık listesi, olay zamanlayıcıları, Y18’deki olay tabanlı güncelleme.

Kaynak: Linux: lib/sort.c

🧰 Kütüphaneler ve araçlar

ad	platform	ne yapar / sınırları	nasıl eklenir
PriorityQueue<TElement, TPriority>	C# (.NET 6+)	İkili yığın (min). Unity’de yok: Unity 6, .NET Standard 2.1 API’sini kullanır; kendi yığınınızı yazın ya da bir port kullanın.	yerleşik (.NET 6+)
PriorityQueue (Unity portu)	Unity	.NET 6 sınıfının Unity’de çalışan kopyası.	GitHub’dan paket
heapq	Python	Liste üzerinde min-yığın fonksiyonları; max için anahtarı ters çevirin.	standart kütüphane
std::priority_queue	C++	Varsayılan olarak max-yığın; min için `std::greater`.	`#include <queue>`
heap-js	JavaScript	JS’te yerleşik yığın yok; küçük, tipli bir yığın kütüphanesi.	`npm install heap-js`

🧩 Oyunlarda öncelik kuyruğu

A* / Dijkstra açık listesi (Y8): en düşük f değerli düğüm.
Olay zamanlayıcısı: “3 sn sonra patlat”, “10 sn sonra yeniden doğ”: en erken olay en önde (Y18).
Yol isteği kuyruğu: yakındaki NPC’lerin isteği önce.
Öncelik değişirse: çoğu kütüphanede “anahtar azalt” yoktur. Pratik çözüm: yeni kaydı ekleyin, eski kayıt çıkınca “bayat mı?” diye kontrol edip atın (tembel silme).

Eşitlik ve sıraYığınlar eşit öncelikli elemanlar için sıra garanti etmez. Aynı anda planlanan iki olayın ekleme sırasıyla çalışması gerekiyorsa önceliğe bir sayaç ekleyin: (zaman, eklemeSırası).

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin

Unity’de PriorityQueue<,> kullanmak (derlenmez)
heapq’dan max-yığın beklemek
Öncelik değişince yığını güncellemeyi unutmak
Eşit önceliklerde sıra garantisi varsaymak

İyi bir istek (prompt) örneği

“Unity 6 (API Compatibility: .NET Standard 2.1), C#. Genel bir ikili min-yığın yaz: BinaryHeap (karşılaştırıcı alan), Push, Pop, Peek, Count; diziyi büyütürken amortize O(1). Üzerine bir EventScheduler: Schedule(float time, Action a) ve Update(float now); eşit zamanlı olaylar ekleme sırasıyla çalışsın; iptal için tembel silme. NUnit testleri ekle.”

Unity sürümünü ve .NET profilini belirtin
Min mi max mı açıkça yazın
Tembel silme (bayat kayıt) kalıbını isteyin
Eşitlikte FIFO için sayaç isteyin

🚀 Proje ve araştırma önerileri

[kolay] Olay zamanlayıcısı — Yeniden doğma, büff süreleri ve tuzakları tek bir yığınla yönetin.
[orta] A* açık listesi — Y8’deki A*’ı kendi ikili yığınınızla yazın; List ile doğrusal arama sürümüne karşı ölçün.
[orta] En iyi 10 — Milyonlarca skor arasından en yüksek 10’u, boyutu 10 olan min-yığınla tek geçişte bulun.
[araştırma] d-li yığınlar — İkili ve 4-lü yığını ölçün; önbellek etkisini açıklayın.

📄 Akademik okumalar ve kaynaklar

Williams 1964 · Algorithm 232: Heapsort (Communications of the ACM 7(6))
İkili yığın ve heapsort.

Floyd 1964 · Algorithm 245: Treesort 3 (Communications of the ACM 7(12))
Doğrusal sürede yığın kurma.

Dijkstra 1959 · A Note on Two Problems in Connexion with Graphs (Numerische Mathematik 1)
Öncelik kuyruğunun en ünlü kullanıcısı.

Neler öğrendik? 🎒

Öncelik kuyruğu: insert + delMax (ya da delMin).
Basit diziler: bir işlem 1, öteki N.
İkili yığın: tam ikili ağaç, dizide; k’nın çocukları 2k, 2k+1.
swim (ekleme) ve sink (çıkarma): ikisi de lg N.

Heapsort: yerinde + en kötü N lg N; introsort’un sigortası.
🎮 Zamanlayıcılar: kökte en yakın olay.
🎮 En iyi k: k elemanlı MIN-yığın, bellek k.
🎮 Olay güdümlü benzetim, A*’ın açık listesi.

Alıştırmalar 🏋️

Kâğıt-kalem: boş bir max-yığına E A S Y Q U E S T I O N ekleyin; her adımda diziyi yazın. Sonra 3 kez delMax yapın.
Dizide sıralı olarak duran bir dizi ([9, 8, 7, …]) her zaman max-yığın mıdır? Peki [1, 2, 3, …]?
Unity’de (ya da p5.js’te) bir zamanlayıcı sistemi yazın: Schedule(delay, action). 10.000 zamanlayıcıyla listeye karşı yığını ölçün.
Bir yığına change(k, yeniÖncelik) işlemi eklemek isteseydiniz (ör. düşmanın tehdit puanı değişti) neye ihtiyaç duyardınız? (İpucu: “eleman şu an dizinin neresinde?” — “indeksli öncelik kuyruğu”)
Heapsort’u [1, 1, 1, …, 1] (hepsi eşit) dizisinde çalıştırın. Karşılaştırma sayısı ne olur?
🤖 Bir YZ asistanından Python’da “en yakın 10 düşmanı” bulan kod isteyin. sorted mı, heapq.nsmallest mi kullandı? Farkı nedir?