Heap'in En Önemli Kullanımı - Öncelik Kuyruğu
Normal bir kuyrukta (queue) "ilk gelen ilk çıkar" kuralı geçerlidir - tıpkı market kasasındaki sıra gibi. Ama bazen bu yeterli olmaz! Örneğin hastane acilinde kalp krizi geçiren birisi, ayak burkan birisinden önce muayene edilmelidir - ne kadar önce gelmiş olursa olsun.
Priority Queue (Öncelik Kuyruğu), her elemanın bir öncelik değeri olduğu özel bir kuyruk türüdür. Normal kuyruktan farklı olarak, en yüksek öncelikli eleman her zaman ilk çıkar - sıraya ne zaman girdiği önemli değil!
İlk gelen ilk çıkar. Öncelik yok, sadece sıra var.
Parantez içi öncelik, ama dikkate alınmıyor
En yüksek öncelikli ilk çıkar. Sıra değil, öncelik önemli!
Düşük sayı = yüksek öncelik (min heap)
Günlük hayatta aslında sürekli priority queue kullanıyoruz:
Priority Queue'yu farklı şekillerde yapabiliriz, ama Heap en verimli yöntemdir:
Şimdi priority queue'nun nasıl çalıştığını gerçek bir hastane acil servisi örneğiyle görelim! Bu simülasyonda hastaları farklı öncelik seviyelerinde ekleyebilir ve min-heap'in onları otomatik olarak nasıl sıraladığını görebilirsiniz.
Priority Queue'yu sıfırdan kendimiz yazmak aslında çok zor değil - daha önce öğrendiğimiz Min Heap yapısını kullanıyoruz. Her eleman (öncelik, veri) şeklinde bir tuple olarak saklanıyor ve heap bize her zaman en küçük öncelikli elemanı O(log n) sürede veriyor.
push(öncelik, veri) → Heap'e ekle, sonra yukarı yüzdür (heapify up)pop() → Kökü al, son elemanı köke koy, aşağı batır (heapify down)peek() → Köke bak ama silme (her zaman en öncelikli eleman köktedir)
class PriorityQueue:
"""Min Heap tabanlı Priority Queue"""
def __init__(self):
self.heap = []
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
def _heapify_up(self, i):
while i > 0:
parent = self._parent(i)
if self.heap[i][0] < self.heap[parent][0]:
self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
i = parent
else:
break
def _heapify_down(self, i):
n = len(self.heap)
while True:
smallest = i
left, right = self._left(i), self._right(i)
if left < n and self.heap[left][0] < self.heap[smallest][0]:
smallest = left
if right < n and self.heap[right][0] < self.heap[smallest][0]:
smallest = right
if smallest != i:
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
i = smallest
else:
break
def push(self, priority, data):
"""Eleman ekle - O(log n)"""
self.heap.append((priority, data))
self._heapify_up(len(self.heap) - 1)
print(f" ➕ Eklendi: [{priority}] {data}")
def pop(self):
"""En yüksek öncelikli (en küçük sayı) çıkar - O(log n)"""
if not self.heap:
return None
result = self.heap[0]
self.heap[0] = self.heap[-1]
self.heap.pop()
if self.heap:
self._heapify_down(0)
return result
def peek(self):
"""Silmeden bak - O(1)"""
return self.heap[0] if self.heap else None
def is_empty(self):
return len(self.heap) == 0
# ========== TEST: Hastane Acil ==========
print("🏥 HASTANE ACİL SERVİSİ")
print("=" * 40)
pq = PriorityQueue()
print("\n📋 Hastalar geldi:")
pq.push(3, "Ali (yüksek ateş)")
pq.push(1, "Ayşe (kalp krizi)") # En kritik!
pq.push(5, "Mehmet (baş ağrısı)")
pq.push(2, "Fatma (kırık kol)")
pq.push(1, "Can (ağır travma)") # Kritik!
print(f"\n📊 Kuyrukta {len(pq.heap)} hasta")
print(f"🔴 Sıradaki: {pq.peek()}")
print("\n" + "=" * 40)
print("🩺 MUAYENE SIRASI (önceliğe göre)")
print("=" * 40)
sira = 1
while not pq.is_empty():
oncelik, hasta = pq.pop()
kritiklik = "🔴" if oncelik == 1 else "🟠" if oncelik == 2 else "🟡" if oncelik == 3 else "🟢"
print(f"{sira}. {kritiklik} [{oncelik}] {hasta}")
sira += 1
print("\n✅ Tüm hastalar muayene edildi!")Python'da priority queue yapmak için kendi sınıfımızı yazmamıza gerek yok! Python'un yerleşik
heapq modülü bize hazır min-heap fonksiyonları sunuyor. Sadece bir liste oluşturup
heappush ve heappop fonksiyonlarını kullanmamız yeterli.
heapq modülü sadece Min Heap destekler!
Max Heap istiyorsanız öncelik değerlerini negatif yapmanız gerekir. Örneğin öncelik 10 için -10 kullanın,
böylece en büyük olan (aslında en küçük negatif) ilk çıkar.
import heapq
print("=== Python heapq ile Priority Queue ===\n")
# Priority Queue = liste + heapq fonksiyonları
pq = []
# Eleman ekle: (öncelik, veri)
# Python tuple'ları ilk elemana göre sıralar
heapq.heappush(pq, (3, "Görev C"))
heapq.heappush(pq, (1, "Görev A - ÖNEMLİ!"))
heapq.heappush(pq, (2, "Görev B"))
heapq.heappush(pq, (1, "Görev A2 - ÖNEMLİ!"))
print(f"Priority Queue: {pq}")
print(f"Sıradaki (peek): {pq[0]}")
# Elemanları öncelik sırasında çıkar
print("\n📋 Görevler sırayla işleniyor:")
while pq:
priority, task = heapq.heappop(pq)
print(f" [{priority}] {task}")
# ===== MAX HEAP İÇİN TRİCK =====
print("\n" + "=" * 40)
print("🔄 MAX HEAP (Negatif Trick)")
print("=" * 40)
max_pq = []
# Negatif öncelik kullan!
heapq.heappush(max_pq, (-10, "Düşük öncelik"))
heapq.heappush(max_pq, (-100, "EN YÜKSEK öncelik"))
heapq.heappush(max_pq, (-50, "Orta öncelik"))
print("\nMax heap sırasıyla:")
while max_pq:
neg_priority, data = heapq.heappop(max_pq)
real_priority = -neg_priority
print(f" [{real_priority}] {data}")Priority Queue'yu üç farklı şekilde gerçekleyebiliriz. Hangisinin en iyi olduğunu anlamak için her bir yaklaşımın zaman karmaşıklığına bakalım:
| İşlem | Heap | Sıralı Dizi | Sırasız Dizi |
|---|---|---|---|
| Push | O(log n) ✅ | O(n) | O(1) |
| Pop | O(log n) ✅ | O(1) | O(n) |
| Peek | O(1) ✅ | O(1) | O(n) |
Sonuç: Eğer sürekli ekleme ve çıkarma yapacaksanız (ki genelde öyledir), Heap açık ara en iyi seçim! O(log n) her iki işlem için de kabul edilebilir bir performans.