Prioritet növbəsində element sıra ilə yox, prioritetlə çıxır: həmişə ən kiçik prioritetli. Bu, tapşırıq planlaşdırıcılarının, Dijkstra-nın və "ən böyük k" məsələlərinin əsasıdır. Bu dərsdə ADT-ni, üç reallaşdırmanı və heapq-nin praktik istifadəsini görürük.
ADT: push və pop_min
ADT üç əməliyyat verir: push(priority, item), pop_min() (extract-min) və peek(). Sıradan fərqli olaraq çıxış ardıcıllığı daxil olma vaxtından yox, prioritetdən asılıdır. Prioritet kiçik olduqca element daha vacibdir; böyük prioritet istəsək, işarəni dəyişirik.
Üç reallaşdırma
Sıralanmamış siyahıda push O(1)-dir, amma pop_min skan edir. Sıralı siyahıda bisect.insort yeri O(log n)-də tapır, amma elementləri sürüşdürməyə O(n) gedir (bisect). İkili yığın hər ikisini O(log n)-ə endirir: ağac massivdə saxlanılır, valideyn uşaqlardan kiçik olur, minimum h[0]-dadır (yığınlar).
