2.38. Antrian prioritas¶

Antrian prioritas adalah wadah yang selalu mengetahui item mana yang terkecil (atau terbesar) tanpa mengurutkan semuanya. heapq mengimplementasikannya di MicroPython menggunakan list biasa sebagai penyimpanan dan algoritma berbasis pohon yang disebut min-heap untuk menjaga item terkecil di indeks 0.

2.38.1. Model mental¶

Min-heap adalah daftar yang diatur sedemikian rupa sehingga item di setiap indeks lebih kecil atau sama dengan item di indeks 2*i + 1 dan 2*i + 2. Pengaturan itu membuat tiga operasi menjadi murah:

Menemukan item terkecil -- ada di heap[0]. Pencarian indeks tunggal, tanpa pemindaian.
Menambahkan item -- ia naik melalui pohon, membandingkan dengan satu induk per level. Seribu item membutuhkan sekitar sepuluh perbandingan; satu juta sekitar dua puluh.
Menghapus item terkecil -- perjalanan yang sama secara terbalik, dengan jumlah perbandingan yang sama.

Daftar tidak diurutkan. Iterasi di atasnya memberikan item dalam urutan sembarang. Hanya heap[0] yang dijamin menjadi minimum.

2.38.2. Tiga fungsi di MicroPython¶

MicroPython's heapq mengekspos tepat tiga fungsi:

heapq.heappush() -- menyisipkan item, menjaga invarian heap tetap utuh.
heapq.heappop() -- menghapus dan mengembalikan item terkecil.
heapq.heapify() -- menyusun ulang daftar yang sudah ada menjadi heap di tempat.

Itulah permukaan lengkapnya. heappushpop, heapreplace, nlargest, nsmallest, dan merge milik CPython tidak ada; pola di bawah menunjukkan cara membangun yang umum secara manual.

Mulai dari awal:

>>> 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

Mulai dari data yang sudah ada:

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

Heapify menyentuh setiap item satu kali dan jauh lebih cepat daripada mendorong item yang sama satu per satu.

2.38.3. Top-N dari aliran data¶

Penggunaan alami dari antrian prioritas: melacak item N terbesar dalam aliran yang hanya dapat dibaca satu kali.

Triknya adalah menjaga min-heap berukuran N. Setiap nilai baru didorong masuk; jika heap tumbuh melampaui N, buang yang terkecil. Yang terkecil selalu ada di heap[0], sehingga satu perbandingan memutuskan apakah akan menyimpan atau membuang setiap item yang masuk:

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 tidak pernah tumbuh melampaui N, sehingga setiap nilai yang masuk membutuhkan sejumlah perbandingan yang sama tidak peduli seberapa panjang aliran tersebut. sorted akhir adalah satu-satunya langkah yang biayanya bergantung langsung pada N.

2.38.4. Acara terjadwal¶

Antrian prioritas dari tuple (deadline, payload) adalah bentuk standar untuk penjadwal acara. Tuple dibandingkan secara leksikografis, sehingga tuple dengan deadline terkecil mengambang ke atas secara otomatis:

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)

Jika dua acara berbagi deadline, perbandingan tuple jatuh ke elemen kedua. Untuk payload yang tidak dapat dibandingkan secara alami, tambahkan counter sebagai elemen kedua tuple untuk memaksakan urutan yang stabil:

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

Sekarang perilaku deadline-terkecil-pertama tetap utuh, seri ditentukan oleh counter sehingga tugas yang dijadwalkan lebih awal berjalan lebih dahulu, dan task tidak harus dapat dibandingkan.

2.38.5. Apa yang `heapq` tidak berikan¶

Beberapa pola yang terlihat seharusnya berhasil, tetapi tidak:

Iterasi for x in heap tidak memberikan output yang diurutkan -- urutan dasar daftar adalah tata letak pohon heap. Untuk mengonsumsi heap secara berurutan, gunakan heappop sampai kosong.
Tidak ada cara untuk mengubah prioritas item yang sudah ada di heap. Solusi standar adalah mendorong prioritas baru sebagai entri baru dan menandai yang lama sebagai dibatalkan (lewati saat muncul).
Heap menyimpan referensi ke itemnya, bukan salinan. Mengubah item setelah didorong masuk dapat merusak invarian heap. Gunakan nilai yang tidak dapat diubah (angka, tuple) sebagai kunci perbandingan.

Min-heap pada daftar biasa adalah alat yang tepat untuk pertanyaan "apa yang terkecil" atau "apa yang paling mendesak" pada perangkat embedded kecil. Tiga fungsi, satu daftar, dan heap akan mengurus sisanya.