Materi
Antrean prioritas adalah antrean yang tidak mengeluarkan data menurut urutan datang, melainkan menurut prioritasnya: yang paling mendesak keluar lebih dulu. Struktur yang biasa menjalankannya adalah heap. Min-heap adalah pohon biner yang setiap induknya tidak lebih besar daripada anak-anaknya, sehingga data terkecil selalu berada di akar.
Modul heapq menyimpan heap di dalam list biasa: anak dari posisi k ada di posisi 2k+1 dan 2k+2, dan heap[0] selalu data terkecil. heappush() menambah data lalu menaikkannya sampai aturan induk terpenuhi lagi, dan heappop() mengeluarkan akar lalu menurunkan data pengganti. Keduanya hanya menyusuri satu jalur dari akar ke daun, jadi biayanya sebanding dengan tinggi heap, sekitar log₂ n. heapify() mengubah list yang sudah ada menjadi heap dalam waktu linear.
import heapq
antre = [5, 3, 8, 1, 2]
heapq.heapify(antre)
print(antre) # [1, 2, 8, 3, 5]: heap, belum urut
print(heapq.heappop(antre)) # 1
print(heapq.nsmallest(2, [7, 4, 9, 1])) # [1, 4]heapq hanya menyediakan min-heap. Untuk mengeluarkan yang terbesar lebih dulu, simpan nilai negatifnya, atau pakai heapq.nlargest dan nsmallest untuk mengambil k data teratas tanpa mengurutkan seluruh daftar. Data yang punya prioritas disimpan sebagai tuple (prioritas, data), karena tuple dibandingkan dari elemen pertama.
