PriorityQueue ve ArrayDeque Detaylı

Bu ders, Queue/Deque dersinde tanıştığımız iki yapıyı derinlemesine inceliyor: PriorityQueue ve ArrayDeque. PriorityQueue elemanları öncelik sırasına göre çıkarır — en yüksek (veya en düşük) öncelikli her zaman önce. ArrayDeque ise hem kuyruk hem yığın olarak kullanılan çok yönlü ve performanslı bir yapı.

Analoji: PriorityQueue bir acil servis triaj sistemi gibi. Hastalar sırayla gelmez — kalp krizi geçiren, parmağını kesen, baş ağrısı olan. Kim daha acilse o önce alınır. Normal kuyrukta sıra önemli, PriorityQueue'da öncelik önemli.

PriorityQueue Temelleri

PriorityQueue, elemanları doğal sıralama (Comparable) veya verdiğin Comparator'a göre önceliklendirir. Arka planda min-heap veri yapısı kullanır.

// Default: doğal sıralama (küçük önce)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);
pq.offer(5);

System.out.println(pq.poll()); // 5 — en küçük
System.out.println(pq.poll()); // 10
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

Dikkat: PriorityQueue'yu iterate etmek sıralı sonuç vermez! Sadece poll() sıralı döner.

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(30, 10, 20, 5));

// İterasyon — SIRALI DEĞİL!
for (int n : pq) {
    System.out.print(n + " "); // 5 10 20 30 olmayabilir! Heap sırası.
}

// Sıralı almak için poll() kullan
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " "); // 5 10 20 30 — garantili sıralı
}

⚠️ Önemli: PriorityQueue'da toString() veya for-each ile gördüğün sıra, gerçek öncelik sırası değildir. Heap'in iç yapısını görürsün. Sıralı erişim sadece poll() ile.

Min-Heap Yapısı

PriorityQueue arka planda binary min-heap kullanır. Bu bir ağaç yapısı, ama dizide saklanır:

// Heap yapısı (dizi olarak: [5, 10, 20, 30])
//        5          ← kök (en küçük)
//       / \
//     10   20
//    /
//   30

// Parent index: (i-1) / 2
// Sol çocuk: 2*i + 1
// Sağ çocuk: 2*i + 2

Performans:

Max-Heap: Büyük Önce

Default olarak PriorityQueue min-heap'tir (küçük değer = yüksek öncelik). Büyük değerlerin önce çıkmasını istiyorsan:

// Max-heap — büyük önce
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
maxPQ.offer(10);
maxPQ.offer(30);
maxPQ.offer(20);

System.out.println(maxPQ.poll()); // 30 — en büyük
System.out.println(maxPQ.poll()); // 20
System.out.println(maxPQ.poll()); // 10

Custom Priority

Kendi nesnelerini önceliklendirmek için Comparator kullan:

public class Task {
    String name;
    int priority; // Düşük sayı = yüksek öncelik
    
    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }
    
    @Override
    public String toString() {
        return name + "(p=" + priority + ")";
    }
}

PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(t -> t.priority)
);

taskQueue.offer(new Task("Rapor yaz", 3));
taskQueue.offer(new Task("Sunucu düzelt", 1));   // En acil
taskQueue.offer(new Task("Mail oku", 5));
taskQueue.offer(new Task("Deploy yap", 2));

while (!taskQueue.isEmpty()) {
    System.out.println(taskQueue.poll());
}
// Sunucu düzelt(p=1)
// Deploy yap(p=2)
// Rapor yaz(p=3)
// Mail oku(p=5)

Çoklu kriter:

// Önce önceliğe göre, eşitse isme göre
PriorityQueue<Task> pq = new PriorityQueue<>(
    Comparator.comparingInt((Task t) -> t.priority)
              .thenComparing(t -> t.name)
);

PriorityQueue Kuralları ve Kısıtlamalar

PriorityQueue<String> pq = new PriorityQueue<>();

// null eklenemez
// pq.offer(null); // NullPointerException!

// Comparable olmayan nesne eklenemez (Comparator vermezsen)
// PriorityQueue<Object> pq2 = new PriorityQueue<>();
// pq2.offer(new Object()); // ClassCastException!

// Thread-safe DEĞİL
// Multi-thread → PriorityBlockingQueue kullan

Gerçek Dünya: En Büyük/Küçük K Eleman

PriorityQueue'nun klasik kullanımı: büyük veri setinden en büyük/küçük K elemanı bulmak.

// En büyük 3 puanı bul
public static List<Integer> topK(int[] scores, int k) {
    // Min-heap — en küçüğü tepede tut
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int score : scores) {
        minHeap.offer(score);
        if (minHeap.size() > k) {
            minHeap.poll(); // En küçüğü at
        }
    }
    
    // Heap'te kalan K eleman en büyükler
    return new ArrayList<>(minHeap);
}

int[] scores = {85, 92, 67, 78, 95, 88, 73, 99};
System.out.println(topK(scores, 3)); // [92, 95, 99] (sırasız olabilir)

💡 İpucu: Top-K problemi için heap boyutunu K'da tutarak O(n log k) karmaşıklık elde edersin. Tüm diziyi sıralamak O(n log n) — K küçükse heap çok daha verimli.

ArrayDeque Detaylı

ArrayDeque, dairesel (circular) dizi kullanan bir Deque implementasyonu. Hem Queue hem Stack olarak kullanılabilir ve her iki senaryoda da LinkedList'ten daha hızlı.

// Dairesel dizi mantığı
// Kapasite: 8, head=2, tail=6
// [_, _, A, B, C, D, _, _]
//         ^head      ^tail

// Başa ekle: head-- → [_, X, A, B, C, D, _, _]
// Sona ekle: tail++ → [_, X, A, B, C, D, E, _]

// Dizi dolunca 2 katına büyür

Deque<String> deque = new ArrayDeque<>(8); // Başlangıç kapasitesi

// Queue olarak (FIFO)
deque.offer("A");     // Sona ekle
deque.offer("B");
deque.offer("C");
deque.poll();          // "A" — baştan çıkar

// Stack olarak (LIFO)
deque.push("X");       // Başa ekle (= addFirst)
deque.push("Y");
deque.pop();           // "Y" — baştan çıkar (= removeFirst)

ArrayDeque vs LinkedList Performans

// Benchmark (konseptual — gerçek benchmark için JMH kullan)
int n = 1_000_000;

// ArrayDeque — Queue olarak
Deque<Integer> aq = new ArrayDeque<>();
for (int i = 0; i < n; i++) aq.offer(i);  // Hızlı — ardışık bellek
while (!aq.isEmpty()) aq.poll();            // Hızlı

// LinkedList — Queue olarak
Deque<Integer> ll = new LinkedList<>();
for (int i = 0; i < n; i++) ll.offer(i);  // Yavaş — her node ayrı nesne
while (!ll.isEmpty()) ll.poll();            // Yavaş — garbage collection yükü

ArrayDeque'nin tek dezavantajı: null kabul etmemesi ve List interface'ini implement etmemesi (index erişimi yok).

ArrayDeque as Stack — Neden Stack Sınıfından İyi?

// Stack sınıfı (KULLANMA)
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.get(0);       // Random access — stack değil bu!
stack.add(0, 99);   // Ortaya ekleme — stack değil bu!
// + synchronized overhead

// ArrayDeque (KULLAN)
Deque<Integer> stack2 = new ArrayDeque<>();
stack2.push(1);
// stack2.get(0);    // Method yok — gerçek stack davranışı

ArrayDeque as Queue — Neden LinkedList'ten İyi?

// LinkedList Queue olarak
Queue<String> q1 = new LinkedList<>();
// Her offer() yeni Node nesnesi oluşturur
// Her poll() Node nesnesini çöpe atar → GC baskısı

// ArrayDeque Queue olarak
Queue<String> q2 = new ArrayDeque<>();
// Mevcut dizide head/tail pointer'ları hareket eder
// Yeni nesne oluşturmak yok — çok daha az GC

Kullanım Rehberi

// FIFO Kuyruk ihtiyacı
Queue<Task> taskQueue = new ArrayDeque<>();

// LIFO Stack ihtiyacı
Deque<String> stack = new ArrayDeque<>();

// Öncelikli kuyruk ihtiyacı
Queue<Task> priorityQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::getPriority)
);

// Çift uçlu kuyruk ihtiyacı
Deque<String> deque = new ArrayDeque<>();

// Thread-safe kuyruk
Queue<Task> concurrentQueue = new ConcurrentLinkedQueue<>();

// Thread-safe öncelikli kuyruk
Queue<Task> blockingPQ = new PriorityBlockingQueue<>();

PriorityQueue vs TreeSet

İkisi de sıralı tutar ama farklı amaçları var:

// Duplicate önemli + sadece "en küçük" lazım → PriorityQueue
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(5); // İkisi de eklenir

// Unique + tüm elemanlar sıralı → TreeSet
TreeSet<Integer> ts = new TreeSet<>();
ts.add(5);
ts.add(5); // İkincisi eklenmez

Gerçek Dünya: Medyan Bulma (İki Heap)

public class MedianFinder {
    // Sol taraf: max-heap (büyük elemanlar tepede)
    private PriorityQueue<Integer> left = new PriorityQueue<>(Comparator.reverseOrder());
    // Sağ taraf: min-heap (küçük elemanlar tepede)
    private PriorityQueue<Integer> right = new PriorityQueue<>();
    
    public void addNum(int num) {
        left.offer(num);
        right.offer(left.poll()); // Sol'un en büyüğünü sağa geçir
        
        if (right.size() > left.size()) {
            left.offer(right.poll()); // Dengeleme
        }
    }
    
    public double findMedian() {
        if (left.size() > right.size()) {
            return left.peek();
        }
        return (left.peek() + right.peek()) / 2.0;
    }
}

MedianFinder mf = new MedianFinder();
mf.addNum(1);
mf.addNum(2);
System.out.println(mf.findMedian()); // 1.5
mf.addNum(3);
System.out.println(mf.findMedian()); // 2.0

Özet

• PriorityQueue min-heap tabanlı — poll() her zaman en düşük öncelikli elemanı döner, iterasyon sıralı değildir

• Max-heap için new PriorityQueue<>(Comparator.reverseOrder()) kullan

• Custom priority için Comparator ver — Comparator.comparingInt(Task::getPriority)

• ArrayDeque dairesel dizi tabanlı — Queue ve Stack olarak LinkedList'ten her zaman daha hızlı (cache-friendly, az GC)

• Stack sınıfını kullanma → Deque<E> stack = new ArrayDeque<>() ile push/pop

• Top-K problemi PriorityQueue'nun klasik kullanım alanı — heap boyutunu K'da tutarak O(n log k) verimlilik