2.38. Öncelik kuyrukları¶

Öncelik kuyruğu, öğelerinden hangisinin en küçük (veya en büyük) olduğunu tüm yapıyı sıralamadan her zaman bilen bir kapsayıcıdır. heapq, MicroPython’da depolama olarak düz bir list ve en küçük öğeyi 0 indeksinde tutmak için min-heap adı verilen ağaç tabanlı bir algoritma kullanarak bunu uygular.

2.38.1. Zihinsel model¶

Min-heap, her indeksteki öğenin 2*i + 1 ve 2*i + 2 indekslerindeki öğelerden küçük-veya-eşit olacak şekilde düzenlenmiş bir listedir. Bu düzenleme üç işlemi ucuz hale getirir:

En küçük öğeyi bulmak – bu heap[0] konumundadır. Tek bir indeks araması, tarama yok.
Bir öğe eklemek – ağaçta yukarı doğru kabarcıklanır, her seviyede bir ebeveynle karşılaştırılır. Bin öğe yaklaşık on karşılaştırmadır; bir milyon yaklaşık yirmi.
En küçük öğeyi kaldırmak – aynı yürüyüşün tersi, aynı sayıda karşılaştırmayla.

Liste sıralı değildir. Üzerinde yineleme yapmak öğeleri rastgele sırada verir. Yalnızca heap[0] öğesinin minimum olduğu garanti edilir.

2.38.2. MicroPython’daki üç fonksiyon¶

MicroPython’un heapq modülü tam olarak üç fonksiyon sunar:

heapq.heappush() – bir öğe ekler, heap değişmezini bozmadan korur.
heapq.heappop() – en küçük öğeyi kaldırır ve döndürür.
heapq.heapify() – mevcut bir listeyi yerinde bir heap’e yeniden düzenler.

Tüm yüzey budur. CPython’un heappushpop, heapreplace, nlargest, nsmallest ve merge fonksiyonları yoktur; aşağıdaki kalıplar yaygın olanların elle nasıl oluşturulacağını gösterir.

Sıfırdan başlamak:

>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, 5)
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 3)
>>> heap
[1, 5, 3]
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
3
>>> heapq.heappop(heap)
5

Mevcut verilerden başlamak:

>>> samples = [5, 1, 3, 2, 4]
>>> heapq.heapify(samples)
>>> samples
[1, 2, 3, 5, 4]
>>> heapq.heappop(samples)
1

Heapify her öğeye bir kez dokunur ve aynı öğeleri tek tek eklemekten gözle görülür şekilde daha hızlıdır.

2.38.3. Bir akış üzerinde Top-N¶

Öncelik kuyruğunun doğal bir kullanımı: yalnızca bir kez okuyabileceğiniz bir akıştaki en büyük N öğeyi takip etmek.

İşin püf noktası, N boyutunda bir min-heap tutmaktır. Her yeni değer eklenir; heap N‘i aşarsa en küçüğü atılır. En küçük her zaman heap[0] konumundadır, bu nedenle tek bir karşılaştırma her gelen öğenin tutulup tutulmayacağına karar verir:

def top_n_brightest(readings, n):
    heap = []
    for r in readings:
        if len(heap) < n:
            heapq.heappush(heap, r)
        elif r > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, r)
    return sorted(heap, reverse=True)

Heap asla N‘i aşmaz, bu nedenle her gelen değer akış ne kadar uzun olursa olsun aynı sayıda karşılaştırmaya mal olur. Son sorted, maliyeti doğrudan N‘e bağlı olan tek adımdır.

2.38.4. Zamanlanmış olaylar¶

(deadline, payload) demetlerinden oluşan bir öncelik kuyruğu, bir olay zamanlayıcısı için standart biçimdir. Demetler sözlükbilimsel olarak karşılaştırılır, bu nedenle en küçük son tarihe sahip demet otomatik olarak en üste çıkar:

import heapq
import time

queue = []
heapq.heappush(queue, (time.time() + 5, 'check sensors'))
heapq.heappush(queue, (time.time() + 1, 'blink LED'))
heapq.heappush(queue, (time.time() + 3, 'send heartbeat'))

while queue:
    deadline, task = queue[0]
    now = time.time()
    if now < deadline:
        time.sleep(deadline - now)
    heapq.heappop(queue)
    run(task)

İki olay aynı son tarihi paylaşıyorsa, demet karşılaştırması ikinci öğeye geçer. Doğal olarak karşılaştırılabilir olmayan yükler için, kararlı bir sıralama zorlamak amacıyla demetin ikinci öğesi olarak bir sayaç ekleyin:

counter = 0
def schedule(deadline, task):
    global counter
    counter += 1
    heapq.heappush(queue, (deadline, counter, task))

Artık önce-en-küçük-son-tarih davranışı korunur, eşitlikler sayaçta çözülür, böylece daha önce zamanlanan görevler önce çalışır ve task öğesinin karşılaştırılabilir olması gerekmez.

2.38.5. `heapq` size neyi vermez¶

Çalışması gerekiyormuş gibi görünen ancak çalışmayan birkaç kalıp:

for x in heap ile yineleme yapmak sıralı çıktı vermez – listenin altta yatan sırası heap’in ağaç düzenidir. Heap’i sırayla tüketmek için boşalana kadar heappop kullanın.
Heap’te zaten bulunan bir öğenin önceliğini değiştirmenin bir yolu yoktur. Standart çözüm, yeni önceliği yeni bir giriş olarak eklemek ve eskisini iptal edilmiş olarak işaretlemektir (geri çıktığında atlayın).
Heap, öğelerinin kopyalarını değil referanslarını depolar. Bir öğeyi eklendikten sonra değiştirmek heap değişmezini bozabilir. Karşılaştırma anahtarı olarak değişmez değerler (sayılar, demetler) kullanın.

Düz bir liste üzerindeki min-heap, küçük bir gömülü cihazda “en küçük nedir” veya “en acil olan nedir” sorularının tümü için doğru araçtır. Üç fonksiyon, bir liste ve gerisini heap halleder.