Öncelik kuyruğu: heap ile PriorityQueue

Öncelik kuyruğu (priority queue) sıradan kuyruğun “ilk gelen ilk çıkar” kuralını bırakır. Her eleman bir öncelik taşır ve her seferinde en öncelikli olan çıkar. Hastanenin acil servisi, işletim sisteminin işlem zamanlayıcısı, Dijkstra algoritması hep bunu kullanır. Geçen hafta binary heap’i bir veri yapısı olarak gördün. Bu hafta onu bir soyut veri tipinin (ADT) gerçekleştirmesi olarak kullanıyoruz ve Java’nın hazır PriorityQueue sınıfını tanıyoruz.

Sınavda bu konudan üç tip soru gelir:

1. İz sürme: “Bu elemanları ekle, iki kez deleteMin yap, diziyi yaz.”
2. “What is printed?”: PriorityQueue ile kısa kod. En büyük tuzak System.out.println(pq).
3. Uygulama + Big-O: “k. en büyüğü bul”, “k listeyi birleştir”, hangi heap ve hangi karmaşıklık.

Öncelik kuyruğu ADT’si

İşlemler:

Neden heap? Diğer seçeneklerle karşılaştır:

AVL de aynı Big-O’yu verir ama işaretçilerle uğraşır, rotasyon yapar. Heap tek bir dizidir, işaretçi yoktur, kod kısadır. Öncelik kuyruğu için standart seçim budur.

Hatırlatma: 1-indeksli min-heap

Ders kitabının kullandığı gösterim: kök array[1], i indeksindeki düğümün çocukları 2i ve 2i+1, ebeveyni i/2. Heap-order kuralı: her ebeveyn çocuklarından küçük ya da eşittir.

insert (percolate up): Elemanı dizinin sonuna koy. Ebeveyninden küçük olduğu sürece yer değiştir.

deleteMin (percolate down): Kökü çıkar. Son elemanı köke taşı. Küçük çocuğundan büyük olduğu sürece küçük çocukla yer değiştir.

Örnek: boş heap’e 10, 4, 7, 1, 8, 3 ekle.

insert 10 -> [10]
insert 4  -> [4, 10]
insert 7  -> [4, 10, 7]
insert 1  -> [1, 4, 7, 10]
insert 8  -> [1, 4, 7, 10, 8]
insert 3  -> [1, 4, 3, 10, 8, 7]

Son hali ağaç olarak:

          1
        /   \
       4     3
      / \   /
    10   8 7

Şimdi iki kez deleteMin:

deleteMin 1 -> [3, 4, 7, 10, 8]
deleteMin 3 -> [4, 8, 7, 10]

İkincisini açalım. 3 çıkar, son eleman 8 köke gelir. Çocuklar 4 ve 7, küçüğü 4 ve 4 < 8, yer değiştir. 8 artık indeks 2’de, tek çocuğu 10 (indeks 4). 10 > 8, dur.

TUZAK · deleteMin’de büyük çocukla değiştirmek. Min-heap’te aşağı süzerken küçük çocukla yer değiştirirsin. Büyükle değiştirirsen küçük çocuk yeni ebeveyninden küçük kalır ve heap kuralı bozulur.

Java’da PriorityQueue

java.util.PriorityQueue<E> bir binary heap’tir. İki fark var: dizi 0-indekslidir (ebeveyn (i-1)/2, çocuklar 2i+1, 2i+2) ve varsayılan olarak min-heaptir.

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{5, 1, 8, 3, 2}) pq.offer(x);
System.out.println(pq);            // iç dizi!
for (int x : pq) System.out.print(x + " ");
System.out.println();
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");

[1, 2, 8, 5, 3]
1 2 8 5 3 
1 2 3 5 8 

TUZAK · println(pq) sıralı değildir. toString() ve for-each döngüsü heap’in iç dizisini sırayla dolaşır. Sadece ilk elemanın en küçük olduğu garantidir. Sıralı çıktı istiyorsan poll() döngüsü kullan. Sınavda [1, 2, 3, 5, 8] yazan puanı kaybeder.

Max-heap ve Comparator

Max-heap için ters sıralayıcı ver:

PriorityQueue<Integer> mx = new PriorityQueue<>(Collections.reverseOrder());
for (int x : new int[]{5, 1, 8, 3, 2}) mx.offer(x);
System.out.println(mx.peek() + " " + mx);

8 [8, 3, 5, 1, 2]

Kendi sıralama kuralın için Comparator ver. Uzunluğa göre, eşitse alfabetik:

PriorityQueue<String> ps = new PriorityQueue<>(
    Comparator.comparingInt(String::length)
              .thenComparing(Comparator.naturalOrder()));
for (String s : new String[]{"pear","fig","apple","kiwi","date","plum"})
    ps.offer(s);
while (!ps.isEmpty()) System.out.print(ps.poll() + " ");

fig date kiwi pear plum apple 

Lambda ile de yazılır: new PriorityQueue<>((a, b) -> b - a) max-heap verir. Ama b - a çok büyük sayılarda taşabilir (overflow); Integer.compare(b, a) daha güvenlidir.

TUZAK · PriorityQueue kararlı değildir. Eşit öncelikli iki eleman eklenme sırasıyla çıkmak zorunda değil. FIFO istiyorsan Comparator’a ikinci kural ekle: ekleme sıra numarası ya da isim.

Uygulama 1: k. en büyük ve k en küçük

n elemanın k. en büyüğünü bulmanın üç yolu:

Üçüncüsü veri akışında (stream) da çalışır: veriyi baştan bilmen gerekmez, bellek $O(k)$. Fikir: heap’te o ana kadarki en büyük k eleman durur. Kök bunların en küçüğüdür. Yeni eleman gelince ekle, boyut k’yı geçerse kökü at.

static int kthLargest(int[] a, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int x : a) {
        pq.offer(x);
        if (pq.size() > k) pq.poll();
    }
    return pq.peek();
}

{7, 2, 9, 4, 11, 5, 3} ve k = 3 için izle:

oku 7  -> {7}
oku 2  -> {2,7}
oku 9  -> {2,7,9}
oku 4  -> {2,4,7,9}  boyut 4 > 3, at 2 -> {4,7,9}
oku 11 -> {4,7,9,11} at 4 -> {7,9,11}
oku 5  -> {5,7,9,11} at 5 -> {7,9,11}
oku 3  -> {3,7,9,11} at 3 -> {7,9,11}
cevap peek = 7

Simetrik kural: k en küçük için max-heap, k en büyük için min-heap. Heap’in kökü “kapıdaki bekçi”dir; içeri girmeye aday olanı onunla karşılaştırırsın.

Uygulama 2: k sıralı listeyi birleştirmek

Merge sort’ta iki listeyi birleştirmeyi biliyorsun. k liste olunca her adımda k başın en küçüğünü bulmak gerekir. Bunu heap yapar: her listenin ilk elemanını heap’e koy. Poll ettiğin eleman hangi listeden geldiyse o listenin bir sonraki elemanını ekle.

// heap elemanı: {değer, listeNo, indeks}
PriorityQueue<int[]> pq =
    new PriorityQueue<>((p, q) -> Integer.compare(p[0], q[0]));
for (int i = 0; i < lists.size(); i++)
    if (!lists.get(i).isEmpty())
        pq.offer(new int[]{lists.get(i).get(0), i, 0});
List<Integer> out = new ArrayList<>();
while (!pq.isEmpty()) {
    int[] t = pq.poll();
    out.add(t[0]);
    int j = t[2] + 1;
    if (j < lists.get(t[1]).size())
        pq.offer(new int[]{lists.get(t[1]).get(j), t[1], j});
}

[1,5,9], [2,6], [3,4,10] için çıktı:

[1, 2, 3, 4, 5, 6, 9, 10]

Heap’te hiçbir zaman k’dan fazla eleman yoktur. N toplam eleman için süre $O(N \log k)$. Büyük dosyaları parça parça sıralayıp birleştiren harici sıralama (external sorting) bu fikre dayanır.

Uygulama 3: zamanlama ve olay simülasyonu

İş zamanlama (scheduling): İşletim sistemi bekleyen işleri önceliğe göre tutar. Her seferinde en öncelikli iş çalışır. Comparator’da önce öncelik, eşitse isim ya da geliş sırası:

record Job(String name, int prio) {}
PriorityQueue<Job> jq = new PriorityQueue<>(
    Comparator.comparingInt(Job::prio).thenComparing(Job::name));
jq.offer(new Job("C", 2)); jq.offer(new Job("A", 3));
jq.offer(new Job("D", 1)); jq.offer(new Job("B", 1));
while (!jq.isEmpty()) System.out.print(jq.poll().name() + " ");

B D C A 

Olay güdümlü simülasyon (event-driven simulation): Bir banka gişesini simüle ettiğini düşün. Saniye saniye ilerlemek yerine olayları (“müşteri geldi”, “müşteri ayrıldı”) zamanlarına göre bir min-heap’e koyarsın. Her adımda en erken olayı çekersin, saat doğrudan o ana atlar. Olay yeni olay doğurabilir: “geldi” olayı işlenince hizmet bitiş zamanında bir “ayrıldı” olayı eklenir. Üç müşteri t = 0, 1, 2’de gelsin, tek gişe, hizmet 4 dakika:

t=0  arrive0  -> leave0 olayı t=4'e eklenir
t=1  arrive1  -> gişe 4'e kadar dolu, leave1 t=8
t=2  arrive2  -> leave2 t=12
t=4  leave0
t=8  leave1
t=12 leave2

Olay sayısı E ise simülasyon $O(E \log E)$ sürer, simüle edilen zaman ne kadar uzun olursa olsun.

Sık yapılan hatalar

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{5, 1, 8, 3, 2}) pq.offer(x);
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{5, 1, 8, 3, 2}) pq.offer(x);
System.out.println(pq);

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int x : new int[]{5, 1, 8, 3, 2}) pq.offer(x);
pq.poll(); pq.poll();
System.out.println(pq.peek() + " " + pq.size());

PriorityQueue<String> pq = new PriorityQueue<>(
    Comparator.comparingInt(String::length)
              .thenComparing(Comparator.naturalOrder()));
for (String s : new String[]{"pear","fig","apple","kiwi","date","plum"})
    pq.offer(s);
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");

PriorityQueue<Integer> m = new PriorityQueue<>();
m.offer(6); m.offer(2); m.offer(9);
int a = m.poll();
m.offer(1); m.offer(7);
int b = m.poll();
System.out.println(a + " " + b + " " + m.peek() + " " + m.size());

7,2,9 → {2,7,9}
4 ekle → {2,4,7,9}, 2 atılır → {4,7,9}
11 → {4,7,9,11}, 4 atılır → {7,9,11}
5 → 5 eklenip hemen atılır → {7,9,11}
3 → aynı şekilde atılır → {7,9,11}

static int kthLargest(int[] a, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int x : a) {
        pq.offer(x);
        if (pq.size() > k) pq.poll();
    }
    return pq.peek();
}