Priority Queue Nedir? Heap ile Çalışma Mantığı ve Kullanımı

Priority queue, öğelerin geliş sırasına göre değil, belirlenen öncelik değerine göre işlenmesini sağlayan veri yapısı modelidir. Yani bir öğe kuyruğa daha önce eklenmiş olsa bile daha yüksek önceliğe sahip başka bir öğe önce işlenebilir. Bu yapı; acil hastaların değerlendirildiği triyaj sistemleri, önemli belgelerin öne alındığı yazıcı kuyrukları ve görevlerin önem derecesine göre planlandığı yazılımlar için kullanışlıdır.

Normal queue yapısında temel yaklaşım ilk gelen ilk işlenir mantığıdır. Priority queue’da ise sırayı öncelik değeri belirler. Eşit önceliğe sahip öğeler arasında hangi öğenin önce işleneceği kullanılan uygulamaya ve eklenen ek kurallara bağlı olabilir; bu nedenle eşitlik durumunda her zaman geliş sırasının korunacağını varsaymamak gerekir.

Priority Queue Nedir ve Normal Queue’dan Farkı Nasıldır?

Bir kuyruğu, işlem bekleyen öğelerin geçici olarak tutulduğu yapı olarak düşünebilirsin. Örneğin normal bir kuyrukta A, B ve C öğeleri bu sırayla eklenirse genellikle önce A, sonra B, ardından C işlenir. Burada önemli olan öğelerin kuyruğa giriş zamanıdır.

Priority queue’da her öğeyle birlikte bir öncelik değeri bulunur. Sistem, işlem sırası geldiğinde kuyruğun başındaki ilk öğeye değil, öncelik kurallarına göre en uygun öğeye yönelir. Öncelik değeri “aciliyet”, “önem”, “işlem sırası” veya uygulamanın belirlediği başka bir ölçüt olabilir.

Bu farkı günlük hayattan üç senaryoyla düşünebilirsin: Hastane triyajında daha acil durumdaki hasta önce değerlendirilebilir, yazıcı kuyruğunda önemli bir belge sırada öne alınabilir ve görev planlayıcıda kritik bir işlem daha düşük öncelikli işlerden önce çalıştırılabilir. Bu senaryolarda hangi öncelik kuralının seçileceğini ilerleyen bölümlerde ayrıca ele alacağız.

Eşit öncelik konusu da önemlidir. İki öğenin öncelik değeri aynıysa bazı uygulamalar bu öğelerden birini herhangi bir belirlenmiş bağlayıcı kurala göre seçebilir. Geliş sırasını korumak istiyorsan öncelik değerine ek olarak sıra numarası gibi ikinci bir karşılaştırma ölçütü tanımlamak daha öngörülebilir bir sonuç sağlayabilir.

Heap, Priority Queue’nun Öncelikli Öğeyi Nasıl Bulmasını Sağlar?

Priority queue bir soyut veri yapısı ve işlem modelidir; yani “öğeleri önceliklerine göre ekle ve en öncelikli öğeyi al” davranışını tanımlar. Heap ise bu davranışı gerçekleştirmek için kullanılan yaygın veri yapılarından biridir. Başka bir ifadeyle priority queue ne yapılacağını, heap ise bunun nasıl düzenlenebileceğini açıklar.

İki temel heap türü vardır. Min-heap yapısında en küçük öncelik değeri kökte bulunur. Max-heap yapısında ise en büyük öncelik değeri köktedir:

Min-heap              Max-heap

    1                     5
   /                    / 
  3   5                 3   1

Bu örnekte aynı 1, 3 ve 5 değerleri kullanılmıştır. Min-heap, köke 1’i getirerek en küçük değeri öne çıkarır. Max-heap ise kökte 5’i tutarak en büyük değerin önce alınmasını kolaylaştırır. Ancak heap, tüm öğeleri baştan sona tamamen sıralanmış bir liste gibi tutmaz. Temel amacı, öncelikli öğeyi erişilebilir bir kök konumunda düzenlemektir.

Bir uygulamaya başlamadan önce şu kontrol listesini kullan:

• Küçük sayı daha acil anlamına mı geliyor?
• Büyük sayı daha önemli anlamına mı geliyor?
• Eşit önceliklerde geliş sırası korunmalı mı?
• Eşitlik varsa ikinci bir sıralama ölçütü gerekli mi?

Bu kararlar, heap türünü ve öğelerin nasıl karşılaştırılacağını belirler. Konuyu pekiştirmek için algoritmik düşünme ve veri yapıları bilgi testlerini çözerek öncelik mantığını farklı örnekler üzerinde değerlendirebilirsin.

Ekleme ve En Öncelikli Öğeyi Alma Adımları

Bir priority queue’ya yeni öğe eklendiğinde öğe, yalnızca listenin sonuna bırakılmaz; heap düzenini koruyacak konuma taşınır. Min-heap kullanımında en küçük öncelik numarası kökte bulunur. Bu nedenle aşağıdaki örnekte 1 numaralı öncelik, 3 numaralı öncelikten daha acil kabul edilmiştir.

Alma işlemi, kökteki öğenin çıkarılmasıyla başlar. Ardından heap’in sonundaki öğe köke alınır ve daha küçük önceliğe sahip çocuklarla karşılaştırılarak uygun konuma indirilir. Böylece her alma işleminden sonra yeni en öncelikli öğe yine kökte tutulur. Örneğin bu dizide görevler sırasıyla Görev B, Görev C ve Görev A olarak işlenir.

Eşit öncelikli öğelerde yalnızca öncelik numarasına bakarak kesin bir sıra beklemek doğru değildir. Python’un heapq belgelerinde de belirtildiği gibi, eşit öncelikli kayıtların eklenme sırasını korumak için önceliğin yanına benzersiz bir sıra numarası eklenebilir. Böyle bir sıra numarası kullanılmazsa, tuple içindeki sonraki değerler karşılaştırılabilir ve sonuç uygulamanın veri biçimine bağlı hâle gelebilir.

Hangi Durumlarda Priority Queue Tercih Edilmeli?

Priority queue, işlerin geliş sırasından önce bir öncelik kuralına göre işlenmesi gerektiğinde uygundur. Karar verirken önceliğin kim tarafından belirlendiğini, ölçütün açık olup olmadığını ve aynı öncelikteki işlerin nasıl sıralanacağını önceden tanımlamak gerekir.

Öte yandan basit bir başvuru sırası, müşteri talep listesi veya geliş sırasının mutlaka korunması gereken bir iş akışı varsa priority queue yerine normal queue daha doğru olabilir. Çünkü bu tür durumlarda amaç en önemli işi seçmek değil, bekleyenleri adil biçimde sırayla işlemektir.

Karar vermek için şu dört soruyu sorabilirsin:

1. Acil veya diğerlerinden önce işlenmesi gereken işler var mı?
2. Öncelik ölçülebilir ve açık bir kuralla belirlenebiliyor mu?
3. Bir işin önceliği zaman içinde değişebilir mi?
4. Eşit öncelikte adil ve tekrarlanabilir bir sıra kuralı gerekli mi?

Bu sorulara verdiğin yanıtları algoritmaya dönüştürmekte zorlanıyorsan, algoritmik düşünme ve veri yapıları bilgi testleri ile hangi konularda pratik yapman gerektiğini görebilirsin.

Python’da heapq ile Öncelik Kuyruğu Kodlamak

Python’da öncelik kuyruğu oluşturmak için standart kütüphanedeki heapq modülünden yararlanabilirsin. heapq, küçük değerin önce geldiği bir min-heap mantığıyla çalışır. Bu nedenle örneğimizde 1 en yüksek önceliği, 3 ise daha düşük önceliği temsil edecek. heappush() öğeyi kuyruğa ekler, heappop() ise o anda en küçük öncelik değerine sahip öğeyi çıkarır.

Öncelik ve görev adını doğrudan (öncelik, görev) biçiminde saklamak mümkün olsa da eşit önceliklerde Python ikinci öğeyi, yani görev adını karşılaştırmaya çalışabilir. Bu durum görevler karşılaştırılamayan farklı nesneler olduğunda sorun çıkarabilir. Ayrıca eşit öncelikli görevlerin geliş sırasını açıkça yönetmek için araya artan bir sayaç eklemek daha güvenlidir. Böylece yapı (öncelik, sayaç, görev) biçimini alır.

import heapq
import itertools

gorev_kuyrugu = []
sayac = itertools.count()

gorevler = [
    (2, "Raporu hazırla"),
    (1, "Acil e-postayı yanıtla"),
    (3, "Dosyaları düzenle"),
    (1, "Sunucuyu kontrol et"),
]

for oncelik, gorev in gorevler:
    sira = next(sayac)
    heapq.heappush(gorev_kuyrugu, (oncelik, sira, gorev))

while gorev_kuyrugu:
    oncelik, _, gorev = heapq.heappop(gorev_kuyrugu)
    print(f"{oncelik}: {gorev}")

Bu kodda önce öncelik değeri 1 olan görevler çıkarılır. Bu iki görev aynı önceliğe sahip olduğundan sayaç değerleri karşılaştırılır ve kuyruğa daha önce eklenen görev önce işlenir. Ardından öncelik değeri 2, son olarak 3 olan görev gelir.

1: Acil e-postayı yanıtla
1: Sunucuyu kontrol et
2: Raporu hazırla
3: Dosyaları düzenle

Buradaki önemli ayrım şudur: Heap’in iç liste görünümü tamamen sıralı bir liste gibi düşünülmemelidir. Senin için asıl önemli olan, heappop() çağrısında öncelik kuralına uyan öğenin alınmasıdır. Eşit önceliklerde geliş sırasını korumak istiyorsan sayaç gibi açık bir bağlayıcı kural eklemelisin.

Bu örneği değiştirerek görev adlarını, öncelik değerlerini ve ekleme sırasını denemek; veri yapısının davranışını ezberlemekten daha öğreticidir. Veri yapıları ve algoritmik düşünme temelini daha kişiselleştirilmiş biçimde geliştirmek isteyenler için birebir özel ders programı kapsamında bu tür yapıların problem üzerinden incelenmesi mümkündür.

Priority Queue Kullanırken Sık Yapılan Hatalar

Öncelik kuyruğu kullanırken hata çoğu zaman kodun yazımından değil, öncelik kuralının baştan netleştirilmemesinden kaynaklanır. Uygulamaya geçmeden önce aşağıdaki kontrol listesini kullanabilirsin:

• Öncelik yönünü karıştırma: Min-heap yapısında küçük sayı önce çıkar. Senin probleminde büyük sayı daha acilse, bu kuralı doğrudan kullanmak yerine öncelik değerlerini dönüştürmen veya max-heap yaklaşımı tasarlaman gerekir.
• Normal queue gereken yerde priority queue kullanma: Her öğenin geliş sırasına göre işlenmesi gerekiyorsa öncelik kuyruğu gereksiz bir karmaşıklık oluşturabilir. Öncelik kavramı gerçekten iş akışının parçası olmalıdır.
• Eşit öncelikleri tanımlamama: Eşit öncelikli öğelerde geliş sırası korunacak mı, yoksa başka bir ölçüt mü kullanılacak? Bu karar kodda sayaç veya ikinci bir karşılaştırma alanıyla açıkça gösterilmelidir.
• Yalnızca kökü test etme: Kuyruğun ilk çıkan öğesi doğru görünse bile arka arkaya yapılan ekleme ve çıkarma işlemlerini test et. Farklı öncelik sıraları ve eşit öncelikler kullanarak tüm akışı kontrol et.
• Önceliği doğrudan değiştirme: Kuyruğa eklenmiş bir öğenin önceliği değiştiğinde, kullanılan yapının düzenini nasıl koruyacağını düşünmelisin. Eski kaydı güncellemek yerine yeni öncelikle yeniden ekleme ve eski kaydı geçersiz sayma gibi bir yaklaşım gerekebilir.

Sınavda veya projede bir priority queue seçmeden önce şu üç soruya cevap ver: Öncelik kuralım nedir, eşitlikte ne olacak, geliş sırası korunmalı mı? Bu soruların yanıtı net değilse kod yazmaya başlamak yerine problem gereksinimini yeniden analiz et. Doğru veri yapısı seçimi, algoritmik düşünmenin koddan önce gelen adımıdır.

Sık Sorulan Sorular

Priority queue ile normal queue arasındaki temel fark nedir?

Normal queue öğeleri genellikle geliş sırasına göre işler; önce gelen önce çıkar. Priority queue ise öğeleri öncelik değerine göre işler. Bu nedenle daha sonra eklenen bir öğe, önceliği daha yüksekse daha önce işlenebilir.

Min-heap ile max-heap arasında nasıl seçim yapılır?

Çıkışta küçük öncelik değerinin önce gelmesini istiyorsan min-heap, büyük değerin önce gelmesini istiyorsan max-heap yaklaşımı uygundur. Seçim, veri yapısından çok problemin öncelik tanımına bağlıdır.

Eşit öncelikli öğeler hangi sırayla işlenir?

Bu sıra kullanılan uygulamaya ve eklenen bağlayıcı kurala bağlı olabilir. Eşit önceliklerde geliş sırasını korumak istiyorsan artan bir sayaç eklemek gibi açık bir yöntem kullanmalısın.

Priority queue kullanmak yerine normal queue ne zaman tercih edilmelidir?

Öğelerin önem derecesi bulunmuyorsa ve yalnızca geliş sırasına göre işlenmeleri gerekiyorsa normal queue daha uygun bir seçimdir. Böylece gereksiz bir öncelik kuralı tanımlamadan daha anlaşılır bir iş akışı kurabilirsin.

Priority queue kullanmadan önce önceliklerin anlamını, eşitlik davranışını ve işlem sırasını netleştirirsen hem daha doğru hem de daha kolay test edilebilir veri yapıları tasarlayabilirsin.