Öncelik Kuyruğu Nedir?
Normal kuyrukta (FIFO) eleman çıkarma sırası ekleme sırasına bağlıdır: ilk giren ilk çıkar. Ancak gerçek hayatta sıra her zaman ekleme zamanına göre belirlenmez. Acil servis koridorunda kalp krizi geçiren hasta, ayak bileği burkmuş hastadan önce alınır — geliş sırasına bakılmaz. İşte öncelik kuyruğu tam olarak budur: her elemanın bir öncelik değeri vardır ve çıkarma işlemi bu değere göre yapılır.
Normal Kuyruk vs Öncelik Kuyruğu
Normal Kuyruk (FIFO):
Giriş sırasına göre çıkar:
Çıkış: A → B → C
Öncelik Kuyruğu:
Öncelik değerine göre çıkar:
Çıkış: B(1) → C(3) → A(5)
Min-Priority Queue vs Max-Priority Queue
Öncelik kuyruğunun iki varyantı vardır. Fark sadece "öncelikli" kelimesinin tanımındadır:
Min-Priority Queue
En düşük öncelik değerine sahip eleman önce çıkar.
Küçük sayı = yüksek öncelik
Hasta A1 Hasta B3 Hasta C5
İlk çıkan: Hasta A (p=1)
Dijkstra, A*, iş zamanlama (shortest job first)
Max-Priority Queue
En yüksek öncelik değerine sahip eleman önce çıkar.
Büyük sayı = yüksek öncelik
Görev X1 Görev Y3 Görev Z5
İlk çıkan: Görev Z (p=5)
OS process scheduling, Huffman coding, bant genişliği yönetimi
Bu bölümde: Hem min hem max priority queue implementasyonunu göstereceğiz. İkisi arasındaki tek fark, karşılaştırma operatörünün yönüdür ( < vs > ). Temel algoritma aynıdır.
Priority Queue ADT — Arayüz
| Operasyon | Açıklama |
|---|
insert(eleman, öncelik) | Elemanı öncelik değeriyle birlikte kuyruğa ekle |
extractMin() | En düşük öncelikli elemanı çıkar ve döndür (min-PQ) |
extractMax() | En yüksek öncelikli elemanı çıkar ve döndür (max-PQ) |
peek() | En öncelikli elemana bak (çıkarmadan) |
isEmpty() | Kuyruk boş mu? |
Dizi Tabanlı İki Yaklaşım
Öncelik kuyruğunu gerçeklemek için pek çok yol vardır. En basit ikisi sırasız (unsorted) ve sıralı (sorted) dizi kullanmaktır. Her birinin enqueue ve dequeue performansı farklıdır:
Yaklaşım 1: Sırasız Dizi
Ekleme: Sona ekle → O(1)
Çıkarma: Min/max'ı ara, bul, çıkar → O(n)
Lazy yaklaşım: "ekleme kolay, çıkarma pahalı"
Yaklaşım 2: Sıralı Dizi
Ekleme: Doğru yere kaydır → O(n)
Çıkarma: Sondan/baştan al → O(1)
Eager yaklaşım: "ekleme pahalı, çıkarma kolay"
İkisi de O(n)! Her iki yaklaşımda da operasyonlardan biri O(n)'dir. Gerçek performans için ikili yığın (binary heap) kullanılır ve her iki operasyon O(log n) olur. Heap konusu ayrı bir bölümde işlenecek — şimdilik dizi yaklaşımlarını öğrenerek kavramı tam oturtalım.
Yaklaşım 1 — Sırasız Dizi
En basit yöntem: elemanları geldiği sırayla dizinin sonuna ekle (enqueue = O(1)). Çıkarmada tüm diziyi tarayarak en yüksek/düşük öncelikli elemanı bul, çıkar ve son elemanla doldur (dequeue = O(n)).
Yapı Tanımı
#include <stdio.h>
#include <limits.h>
#define MAX 100
typedef struct {
int deger; // elemanın verisi
int oncelik; // öncelik değeri
} PQItem;
typedef struct {
PQItem items[MAX];
int boyut; // mevcut eleman sayısı
} PriorityQueue;
void pqOlustur(PriorityQueue* pq) {
pq->boyut = 0;
}Ekleme (Insert) — O(1)
Algoritma: Yeni elemanı dizinin sonuna ekle, boyutu artır. Sıralama yapmaya gerek yok — çıkarmada arayacağız.
Sırasız Diziye Ekleme — Sona Ekle, Sıralama Yok
Mevcut: boyut = 3
Sıra yok: A(5), B(1), C(3) — geliş sırasında
insert(D, 2) → sona ekle, boyut = 4
O(1) — tek atama, kaydırma yok
void pqInsert(PriorityQueue* pq, int deger, int oncelik) {
if (pq->boyut == MAX) {
fprintf(stderr, "PQ Overflow!\n");
return;
}
pq->items[pq->boyut].deger = deger;
pq->items[pq->boyut].oncelik = oncelik;
pq->boyut++;
}En Düşük Öncelikli Elemanı Çıkarma (extractMin) — O(n)
Algoritma:
1. Tüm diziyi tara, en düşük öncelik değerine sahip elemanı bul.
2. Bu elemanı kaydet.
3. Dizideki son elemanı bu pozisyona kopyala (boşluğu doldur).
4. Boyutu azalt. Kaydedilen değeri döndür.
extractMin — Lineer Tarama ile Min Bulma
① Tüm diziyi tara → min = B (p=1)
n=4 eleman tarandı → O(n)
② B'yi çıkar, son eleman D'yi B'nin yerine koy
Döndürülen: B (değer), boyut: 4 → 3
PQItem extractMin(PriorityQueue* pq) {
if (pq->boyut == 0) {
fprintf(stderr, "PQ Underflow!\n");
PQItem bos = {-1, INT_MAX};
return bos;
}
// En düşük öncelikli elemanı bul
int minIdx = 0;
for (int i = 1; i < pq->boyut; i++) {
if (pq->items[i].oncelik < pq->items[minIdx].oncelik)
minIdx = i;
}
PQItem min = pq->items[minIdx];
// Son elemanı bu pozisyona kopyala
pq->items[minIdx] = pq->items[pq->boyut - 1];
pq->boyut--;
return min;
}En Yüksek Öncelikli Elemanı Çıkarma (extractMax) — O(n)
Max-priority queue için tek fark: tarama sırasında < yerine > kullanmak.
PQItem extractMax(PriorityQueue* pq) {
if (pq->boyut == 0) {
fprintf(stderr, "PQ Underflow!\n");
PQItem bos = {-1, INT_MIN};
return bos;
}
int maxIdx = 0;
for (int i = 1; i < pq->boyut; i++) {
if (pq->items[i].oncelik > pq->items[maxIdx].oncelik)
maxIdx = i;
}
PQItem max = pq->items[maxIdx];
pq->items[maxIdx] = pq->items[pq->boyut - 1];
pq->boyut--;
return max;
}Yaklaşım 2 — Sıralı Dizi
Alternatif strateji: diziyi her zaman sıralı tut. Ekleme sırasında doğru pozisyonu bul ve elemanları kaydır (O(n)), ama çıkarma son elemandan yapılır (O(1)).
Sıralı Diziye Ekleme (Insert) — O(n)
Sıralı Diziye Ekleme — Kaydırmalı Yerleştirme (Azalan sıra, max-PQ)
Mevcut: önceliğe göre azalan sırada [5, 3, 1]
insert(D, 2) → doğru yer: [2] (3 ve 1 arasında). B'yi sağa kaydır.
O(n) — doğru yeri bul + elemanları kaydır (insertion sort mantığı)
Sıralı Diziden Çıkarma — O(1)
Max-PQ: En Büyük Başta → Baştan Çıkar | Min-PQ: En Küçük Sonda → Sondan Çıkar
Max-PQ: Azalan sıra → [0]'dan çıkar
Baştan çıkar ama kaydırma gerekir → O(n) 😟
Min-PQ: Azalan sıra → sondan çıkar
Sondan çıkar → boyut-- → O(1) ✓
Sıralama yönü stratejisi: Diziyi azalan sırada tutarsanız min-PQ'da çıkarma O(1) (sondan al), max-PQ'da ise O(n) (baştan al + kaydır). Diziyi artan sırada tutarsanız tam tersi olur. Pratikte diziyi öyle sıralayın ki hedef eleman sonda kalsın — bu şekilde çıkarma her zaman O(1)'dir.
Sıralı Dizi Kodu (Azalan Sıra — Min-PQ İçin Optimize)
/* ── Sıralı ekleme (azalan sıra) — O(n) ── */
void sortedInsert(PriorityQueue* pq, int deger, int oncelik) {
if (pq->boyut == MAX) {
fprintf(stderr, "PQ Overflow!\n");
return;
}
// Doğru pozisyonu bul (azalan: büyük önce)
int i = pq->boyut - 1;
while (i >= 0 && pq->items[i].oncelik < oncelik) {
pq->items[i + 1] = pq->items[i]; // sağa kaydır
i--;
}
pq->items[i + 1].deger = deger;
pq->items[i + 1].oncelik = oncelik;
pq->boyut++;
}
/* ── Sondan çıkar (en küçük öncelik sonda) — O(1) ── */
PQItem sortedExtractMin(PriorityQueue* pq) {
if (pq->boyut == 0) {
fprintf(stderr, "PQ Underflow!\n");
PQItem bos = {-1, INT_MAX};
return bos;
}
return pq->items[--pq->boyut]; // son eleman = min
}Adım Adım — Min-Priority Queue (Sırasız Dizi)
Acil serviste hasta kabulü senaryosu: hastalar farklı öncelik seviyeleriyle gelir, en düşük öncelik numaralı hasta (en acil) önce alınır.
Acil Servis — insert + extractMin Senaryosu
① insert("Ayak ağrısı", 5)
boyut=1
② insert("Kalp krizi", 1)
boyut=2 — sırasız: Ayak(5), Kalp(1)
③ insert("Kırık kol", 3), insert("Baş ağrısı", 4)
boyut=4 — hâlâ geliş sırasında
④ extractMin() → Kalp krizi (p=1) — en acil hasta
Tara: 5,1,3,4 → min=1 (indeks 1). Son eleman Baş'ı [1]'e kopyala.
🏥 Kalp krizi hastası alındı (geliş sırası: 2., ama en acil!)
⑤ insert("Yanık", 2)
boyut=4 — Yanık sona eklendi
⑥ extractMin() → Yanık (p=2)
Tara: 5,4,3,2 → min=2 (indeks 3). Son eleman zaten indeks 3.
🏥 Yanık hastası alındı
⑦ extractMin() → Kırık kol (p=3), ⑧ extractMin() → Baş ağrısı (p=4)
Kalan: Ayak ağrısı (p=5) — en az acil olan en son alınır
Çıkış sırası: Kalp(1) → Yanık(2) → Kırık(3) → Baş(4) → Ayak(5) ✓
Peek ve isEmpty
int pqIsEmpty(PriorityQueue* pq) {
return pq->boyut == 0;
}
/* ── En düşük öncelikliye bak (çıkarmadan) — O(n) ── */
PQItem peekMin(PriorityQueue* pq) {
if (pq->boyut == 0) {
fprintf(stderr, "PQ Boş!\n");
PQItem bos = {-1, INT_MAX};
return bos;
}
int minIdx = 0;
for (int i = 1; i < pq->boyut; i++)
if (pq->items[i].oncelik < pq->items[minIdx].oncelik)
minIdx = i;
return pq->items[minIdx];
}
/* ── Yazdırma ── */
void pqYazdir(PriorityQueue* pq) {
if (pqIsEmpty(pq)) { printf(" [Boş]\n"); return; }
printf(" [");
for (int i = 0; i < pq->boyut; i++)
printf("(%d,p=%d)%s", pq->items[i].deger,
pq->items[i].oncelik,
i < pq->boyut - 1 ? ", " : "");
printf("]\n");
}Demo Program
int main() {
PriorityQueue pq;
pqOlustur(&pq);
printf("=== Min-Priority Queue (Sırasız Dizi) ===\n\n");
printf("Ekleme:\n");
pqInsert(&pq, 100, 5); printf(" insert(100, p=5) "); pqYazdir(&pq);
pqInsert(&pq, 200, 1); printf(" insert(200, p=1) "); pqYazdir(&pq);
pqInsert(&pq, 300, 3); printf(" insert(300, p=3) "); pqYazdir(&pq);
pqInsert(&pq, 400, 2); printf(" insert(400, p=2) "); pqYazdir(&pq);
pqInsert(&pq, 500, 4); printf(" insert(500, p=4) "); pqYazdir(&pq);
printf("\nPeek min: deger=%d, oncelik=%d\n",
peekMin(&pq).deger, peekMin(&pq).oncelik);
printf("\nÇıkarma (öncelik sırasıyla):\n");
while (!pqIsEmpty(&pq)) {
PQItem item = extractMin(&pq);
printf(" extractMin() → deger=%d, oncelik=%d\n",
item.deger, item.oncelik);
}
printf("\nUnderflow testi:\n");
extractMin(&pq);
return 0;
}=== Min-Priority Queue (Sırasız Dizi) ===
Ekleme:
insert(100, p=5) [(100,p=5)]
insert(200, p=1) [(100,p=5), (200,p=1)]
insert(300, p=3) [(100,p=5), (200,p=1), (300,p=3)]
insert(400, p=2) [(100,p=5), (200,p=1), (300,p=3), (400,p=2)]
insert(500, p=4) [(100,p=5), (200,p=1), (300,p=3), (400,p=2), (500,p=4)]
Peek min: deger=200, oncelik=1
Çıkarma (öncelik sırasıyla):
extractMin() → deger=200, oncelik=1
extractMin() → deger=400, oncelik=2
extractMin() → deger=300, oncelik=3
extractMin() → deger=500, oncelik=4
extractMin() → deger=100, oncelik=5
Underflow testi:
PQ Underflow!
Implementasyon Karşılaştırması
| Operasyon | Sırasız Dizi | Sıralı Dizi | Binary Heap* |
|---|
insert | O(1) ✓ | O(n) | O(log n) |
extractMin/Max | O(n) | O(1) ✓ | O(log n) |
peek | O(n) | O(1) ✓ | O(1) ✓ |
isEmpty | O(1) | O(1) | O(1) |
| Bellek | Dizi (n) | Dizi (n) | Dizi (n) |
| Kod karmaşıklığı | En basit | Orta | Karmaşık |
| En iyi senaryo | Çok fazla insert, nadir extract | Çok fazla extract, nadir insert | Genel amaç |
* Binary heap ayrı bölümde (Ağaç yapıları) detaylı işlenecektir.
n büyüdüğünde fark çarpıcıdır: 1.000.000 elemanlı bir kuyrukta sırasız dizi ile extractMin 1.000.000 karşılaştırma gerektirir. Binary heap ile aynı işlem sadece ~20 karşılaştırma (log₂ 1.000.000 ≈ 20). Bu yüzden pratikte heap tercih edilir, ama kavramı öğrenmek için dizi yaklaşımları idealdir.
Karmaşıklık Analizi — Detaylı
| Operasyon | En İyi | Ortalama | En Kötü | Açıklama |
|---|
insert (sırasız) | O(1) | O(1) | O(1) | Her zaman sona ekle |
extractMin (sırasız) | O(n) | O(n) | O(n) | Her zaman tam tarama |
insert (sıralı) | O(1) | O(n) | O(n) | En iyi: sona eklenirse |
extractMin (sıralı) | O(1) | O(1) | O(1) | Her zaman sondan al |
Gerçek Dünya Kullanım Alanları
Dijkstra Algoritması
En kısa yol algoritması, her adımda en düşük mesafeli düğümü seçer — min-priority queue ile O(V²)'den O(E log V)'ye iner. GPS navigasyonunun kalbi.
OS Process Scheduling
İşletim sistemi çalıştırılacak süreçleri önceliğe göre seçer. Yüksek öncelikli süreç (kernel) düşük öncelikliden (kullanıcı uygulaması) önce CPU alır. Linux CFS scheduler buna dayanır.
Huffman Coding
Veri sıkıştırmada en düşük frekanslı iki düğüm birleştirilerek Huffman ağacı oluşturulur. Her adımda min-PQ'dan iki eleman çıkarılır. ZIP, JPEG, MP3 formatlarının temelindedir.
A* Pathfinding
Oyunlarda ve robot navigasyonunda kullanılan A* algoritması, f(n) = g(n) + h(n) değerine göre düğümleri min-PQ'dan çeker. Her RTS oyununda birliklerin yol bulması buna dayanır.
Neden Binary Heap?
Dizi vs Heap — Performans Karşılaştırması (n eleman)
Sırasız Dizi
insert: O(1)
extract: O(n)
Sıralı Dizi
insert: O(n)
extract: O(1)
Binary Heap ✓
insert: O(log n)
extract: O(log n)
Heap her iki operasyonu da dengeli yapar — her zaman en iyi genel performans
Sonuç
Öncelik kuyruğu, FIFO prensibini kırarak elemanlara öncelik değerine göre hizmet verir. Min-priority queue en düşük öncelikli elemanı, max-priority queue en yüksek öncelikli elemanı önce çıkarır. Dizi tabanlı iki basit yaklaşım vardır: sırasız dizi (O(1) insert, O(n) extract) ve sıralı dizi (O(n) insert, O(1) extract). Her ikisi de öğretici ama n büyüdüğünde yetersizdir.
Gerçek uygulamalarda öncelik kuyruğu neredeyse her zaman binary heap ile gerçeklenir — hem insert hem extract O(log n) olur. Dijkstra, A*, Huffman, OS scheduling ve event-driven simülasyon gibi kritik algoritmalar heap tabanlı priority queue'ya bağımlıdır. Heap yapısını ağaç konusunda ayrıntılı işleyeceğiz.
Bölüm 5.3 özeti: Priority Queue = önceliğe göre çıkarma. Min-PQ: küçük önce, Max-PQ: büyük önce. Sırasız dizi: insert O(1), extract O(n). Sıralı dizi: insert O(n), extract O(1). Gerçek çözüm: binary heap → her ikisi O(log n).