Öncelik Kuyruğu
- İngilizcesi
- Priority Queue
- Türkçe karşılığı
- öncelikli kuyruk
- Okunuşu
- prayorıti kyu
Günlük kullanımda iki ad da yaygın.
Kısaca
Öncelik kuyruğu, her öğenin bir önceliği olduğu ve ne zaman eklendiğine bakılmaksızın en yüksek öncelikli öğenin her zaman önce çıkarıldığı bir koleksiyondur.
Öncelik kuyruğu (priority queue) nedir?
Öncelik kuyruğu, her öğenin bir öncelik taşıdığı bir koleksiyondur ve bir öğeyi çıkardığınızda ilk gelen değil en yüksek önceliğe sahip olan size verilir. Min-öncelik kuyruğunda en küçük değer en acil sayılır, max-öncelik kuyruğunda ise en büyük değer. Temel işlemleri öğe eklemek, tepedeki öğeye bakmak ve tepedeki öğeyi çıkarmaktır; bu sonuncusuna bazen extract-min ya da extract-max denir.
Öncelik kuyruğu bir soyut veri tipidir; yani belleğe nasıl yerleştirildiğini değil, davranışı tanımlar. Standart uygulaması ikili heap'tir: ekleme ve çıkarma O(log n), bakma ise O(1) sürer. Sıralı bir dizi çıkarmayı ucuz ama eklemeyi O(n) yapar, sırasız bir liste ise tersini; bu yüzden heap dengeli seçimdir. Python'ın heapq modülü, Java'nın PriorityQueue ve C++'ın std::priority_queue yapısı gibi birçok dil bir tane sunar; JavaScript'te yerleşik bir tane yoktur, bu yüzden geliştiriciler küçük bir heap yazar ya da kütüphane kullanır.
Acil servis triyaj masası klasik benzetmedir: hastalar aciliyete göre görülür; dolayısıyla ağır yaralı yeni gelen biri, burkulmuş bileğiyle bekleyen birinin önüne geçer. Öncelik kuyrukları işletim sistemi ve iş zamanlayıcılarını, rota planlamadaki Dijkstra algoritmasını ve A* aramasını, sıradaki olayı her zaman zaman sırasına göre işleyen simülasyonları, çok sayıda sıralı dosyanın birleştirilmesini ve devasa bir veri akışından ilk k sonucun tutulmasını yürütür. Mesaj aracıları (message broker) ve arka plan iş sistemleri de çoğu zaman aynı fikre dayanan öncelik düzeyleri sunar.
Öncelik kuyruğu sıklıkla normal kuyruk ve heap ile karıştırılır. Kuyruk kesinlikle ilk giren ilk çıkar sırasıyla çalışır; öncelik kuyruğu ise geliş sırasını yok sayar ve eşit öncelikli öğeler, bir bağ bozucu olarak sıra numarası eklemediğiniz sürece belirli bir sırayla çıkmaz. Heap, öncelik kuyruğu kurmak için en sık kullanılan veri yapısıdır; bu yüzden iki sözcük bazen birbirinin yerine kullanılır, ancak öncelik kuyruğu dengeli bir ağaç ya da başka yapılar üzerine de kurulabilir.
Önemli noktalar
- Öncelik kuyruğu her zaman en eskiyi değil, en yüksek öncelikli öğeyi önce çıkarır.
- Soyut bir veri tipidir ve çoğunlukla ikili heap ile uygulanır.
- Heap ile ekleme ve çıkarma O(log n), bakma O(1) sürer.
- Eşit öncelikli öğelerin, bir bağ bozucu eklemediğiniz sürece garantili bir sırası yoktur.
- Zamanlayıcılar, Dijkstra algoritması ve ilk k sonuç sorguları öncelik kuyruklarına dayanır.
Örnek
import heapq
from itertools import count
queue, arrival = [], count() # the counter breaks ties between equal priorities
def push(priority, task):
heapq.heappush(queue, (priority, next(arrival), task)) # O(log n)
push(2, "send newsletter")
push(1, "charge card")
push(2, "resize images")
push(0, "page the on-call engineer")
while queue:
priority, _, task = heapq.heappop(queue) # O(log n): lowest number first
print(priority, task) # 0 page..., 1 charge..., 2 send..., 2 resize...Sık sorulan sorular
Öncelik kuyruğu ile heap arasındaki fark nedir?
Öncelik kuyruğu soyut davranıştır: öğe ekleyin ve her zaman en önemlisini çıkarın. Heap ise bu davranışı verimli biçimde sağlayan somut bir veri yapısıdır; öncelik kuyruklarının çoğunun heap üzerine kurulmasının nedeni budur.
Öncelik kuyruğunun zaman karmaşıklığı nedir?
İkili heap ile bir öğe eklemek ve tepedekini çıkarmak O(log n), tepedekine bakmak O(1) sürer. Var olan n öğeden bir öncelik kuyruğunu tek seferde oluşturmak O(n) sürer.
JavaScript'te öncelik kuyruğu var mı?
Hayır, JavaScript'te yerleşik bir öncelik kuyruğu yoktur. Bir dizinin üzerine küçük bir ikili heap yazabilir ya da bir kütüphane kullanabilirsiniz; küçük girdilerde her eklemeden sonra diziyi yeniden sıralamak da çalışır, ancak her seferinde O(n log n) maliyetlidir.
İlgili sayfalar
- HeapVeri Yapıları, s. 19Heap, en küçük ya da en büyük öğeyi kökünde tutan ağaç tabanlı bir veri yapısıdır; bu öğeyi O(1)'de okuyabilir ve O(log n)'de çıkarabilirsiniz.
- KuyrukVeri Yapıları, s. 24Kuyruk, öğeleri ilk giren ilk çıkar (FIFO) sırasıyla saklayan bir veri yapısıdır; en uzun süre bekleyen öğe her zaman çıkarılacak sonraki öğedir.
- Dijkstra AlgoritmasıVeri Yapıları, s. 12Dijkstra algoritması, tüm kenar ağırlıkları sıfır ya da pozitifken bir başlangıç düğümünden diğer tüm düğümlere en kısa yolları bulan çizge algoritmasıdır.
- CPU Zamanlamaİşletim Sistemleri, s. 5CPU zamanlama, işletim sisteminin her CPU çekirdeğinde hangi hazır process ya da thread'in ne kadar çalışacağına karar vermesidir; işlemci adil paylaşılır.
- Açgözlü AlgoritmaVeri Yapıları, s. 1Açgözlü algoritma, önceki kararları yeniden düşünmeden her adımda o an en iyi görünen seçimi yaparak çözümü adım adım kuran bir algoritmadır.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin