Öncelikli kuyruk nedir?
- Algoritmalar kursu
- Orta seviye
- Ders 41/80
- 4 dk
Her elemanın önceliği olan kuyruk veri yapısını öğrenirsin.
Öncelikli kuyruk nedir?
Öncelikli kuyruk (priority queue), her elemanın bir önceliği olduğu ve en yüksek (veya en düşük) öncelikli elemanın önce çıktığı bir veri yapısıdır.
Sıradan kuyruktan (FIFO) farklı olarak, çıkarma sırası önceliğe bağlıdır. Heap ile uygulanırsa ekleme ve çıkarma O(log n).
Görev zamanlayıcı, Dijkstra algoritması ve Huffman kodlamasında kullanılır.
Heap ile uygulama
Öncelikli kuyruk en verimli biçimde heap ile uygulanır. Min-heap, en düşük öncelikliyi; max-heap, en yüksek öncelikliyi kökte tutar.
Ekleme: heap'e ekle + sift-up, O(log n). Çıkarma: kökü al + son elemanı köke taşı + sift-down, O(log n).
Peek (köke bakma) O(1). Bu, sıralı diziye göre denge sağlar.
Uygulama Peek
peek(arr) yaz. Kökü (en küçük) döndür. print(peek([1, 3, 2, 5, 4])) ile 1 yazdır.
Başlangıç kodu
def peek(arr):
# Kökü döndürÖrnek çözüm
def peek(arr):
# Kökü döndür
return arr[0]
print(peek([1, 3, 2, 5, 4]))Beklenen çıktı
1
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Öncelikli kuyruk neyi önce çıkarır?
- İlk eklenen
- En yüksek öncelikli Doğru cevap
- Son eklenen
- Rastgele
Açıklama: En yüksek öncelikli
2 Peek
return arr[____]return arr[0]Açıklama: 0 doğru.
3 Öncelikli kuyruk nedir: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Push |
Ekle + sift-up |
Pop |
Kök al + sift-down |
Peek |
Kök oku |
Heap |
Temel |