Yığınlar ve Öncelik Kuyrukları
Öncelik kuyruğu, her zaman en yüksek (veya en düşük) önceliğe sahip öğeyi veren soyut bir veri yapısıdır; yığınlar ise, verimli ekleme ve en küçük öğeyi çıkarma işlemleriyle bunu uygulayan standart ağaç tabanlı yapılardır.
Tanım
Öncelik kuyruğu, öncelikli öğelerin eklenmesini ve en yüksek öncelikli öğenin çıkarılmasını destekleyen soyut bir veri yapısıdır; yığın ise, yığın özelliğini (her düğümün anahtarı çocuklarına göre tutarlı bir şekilde sıralanır) karşılayan ve bir öncelik kuyruğunu verimli bir şekilde uygulayan ağaç tabanlı bir veri yapısıdır.
Kapsam
Bu kapsam, öncelik kuyruğu soyut veri yapısını (ADT) ve onun yığın uygulamalarını ele almaktadır: ikili yığın ve dizi gösterimi, yığın özelliği ve yukarı/aşağı kaydırma (sift-up/sift-down) işlemleri, yığın sıralaması (heapsort) ve anahtar azaltma (key-decrease) ile birleştirme (union) maliyetlerini iyileştiren binom ve Fibonacci yığınları gibi gelişmiş birleştirilebilir yığınlar. Konu, öncelik kuyruklarına dayanan çizge algoritmaları (Dijkstra, Prim) ve olay tabanlı simülasyon ile ilişkilidir.
Temel sorular
- Öncelik kuyruğu soyut veri yapısını (ADT) hangi işlemler tanımlar ve bir yığın bunları nasıl uygular?
- Yığın özelliği, en küçük öğeyi sabit zamanda bulmayı ve ekleme/çıkarma işlemlerini logaritmik zamanda gerçekleştirmeyi nasıl sağlar?
- İkili bir yığın bir dizide nasıl kompakt bir şekilde saklanır ve doğrusal zamanda nasıl oluşturulur?
- Yığın sıralaması (heapsort), O(n log n) zamanda yerinde sıralama yapmak için bir yığını nasıl kullanır?
- Fibonacci yığınları gibi birleştirilebilir yığınlar, anahtarları sık sık azaltan algoritmaları ne zaman iyileştirir?
Anahtar kavramlar
- öncelik kuyruğu soyut veri yapısı (ADT)
- yığın özelliği
- ikili yığın
- dizi tabanlı yığın gösterimi
- yukarı kaydırma ve aşağı kaydırma
- doğrusal zamanda yığın oluşturma
- yığın sıralaması (heapsort)
- Fibonacci ve binom yığınları
Temel kuramlar
- Yığın özelliği ve dizi gösterimi
- İkili bir yığın, her düğümün anahtarının çocuklarının anahtarlarına baskın olduğu neredeyse tam bir ikili ağaçtır; bu, örtük ebeveyn-çocuk indekslemesi ile bir dizide saklanabilir ve O(log n) ekleme ve çıkarma ile O(1) en küçük öğeyi bulma sağlar.
- Fibonacci yığınlarının amortize edilmiş verimliliği
- Fibonacci yığınları, O(1) amortize edilmiş zamanda anahtar azaltmayı (decrease-key) ve O(log n) amortize edilmiş zamanda en küçük öğeyi çıkarmayı destekleyerek, sık sık anahtar azaltma işlemleri yapan Dijkstra ve Prim gibi algoritmaların asimptotik çalışma sürelerini iyileştirmektedir.
Klinik önem
Öncelik kuyrukları temel bir altyapıdır: işletim sistemi zamanlayıcılarında hazır görevleri sıralar, ayrık olay simülasyonunda olayları yönetir, en iyi-ilk (best-first) ve A* aramasını yönlendirir ve Dijkstra ile Prim algoritmalarında sınırı sağlar. Yığın sıralaması (Heapsort), garantili en kötü durum sınırlarına sahip, yerinde (in-place) O(n log n) bir sıralama sunmaktadır.
Tarihçe
J. W. J. Williams, ikili yığını ve yığın sıralamasını (heapsort) 1964 yılında tanıtmıştır ve Robert Floyd kısa bir süre sonra doğrusal zamanlı yığın oluşturma (build-heap) prosedürünü sunmuştur. Binom yığınları (Vuillemin, 1978) ve Fibonacci yığınları (Fredman ve Tarjan, 1987), verimli birleştirmeyi ve amortize edilmiş anahtar azaltmayı (decrease-key) ekleyerek klasik çizge algoritmalarının çalışma sürelerini keskinleştirmiştir.
Öne çıkan isimler
- J. W. J. Williams
- Robert W. Floyd
- Michael Fredman
- Robert Tarjan
İlgili konular
Temel eserler
- williams1964
- fredman1987
- cormen2009
Sıkça sorulan sorular
- İkili bir yığını neden işaretçilerle değil de bir dizide saklarız?
- İkili bir yığın neredeyse tam bir ikili ağaçtır, bu nedenle düğümleri ardışık dizi indekslerine düzgün bir şekilde eşlenir: i indeksindeki bir düğümün çocukları 2i ve 2i+1 indekslerinde bulunur. Bu durum, işaretçi yükünü önler, önbellek davranışını iyileştirir ve gezinmeyi basit aritmetik işlemlerle mümkün kılar.
- Fibonacci yığınları karmaşıklıklarına ne zaman değer?
- Fibonacci yığınları, yoğun çizelgelerdeki Dijkstra'nın en kısa yol algoritmaları gibi algoritmaların asimptotik çalışma süresini iyileştiren O(1) amortize edilmiş anahtar azaltma (decrease-key) sağlar. Pratikte, büyük sabit faktörleri nedeniyle daha basit ikili yığınlar genellikle daha hızlıdır, bu yüzden esas olarak teorik sınırlar ve özel durumlar için önem taşımaktadırlar.