Черга з пріоритетом (англ. Priority queue) - абстрактний тип даних в програмуванні. підтримує дві обов'язкові операції - додати елемент і витягти максимум (мінімум). Передбачається, що для кожного елемента можна обчислити його пріоритет - дійсне число або в загальному випадку елемент лінійно впорядкованої множини.
Основні методи, які реалізуються чергою з пріоритетом, такі:
- insert (ключ, значення) - додає пару (ключ, значення) в сховище;
- extract_minimum () - повертає пару (ключ, значення) з мінімальним значенням ключа, видаляючи її з сховища.
При цьому менше значення ключа відповідає більш високому пріоритету.
У деяких випадках більш природний ріст ключа разом з пріоритетом. Тоді другий метод можна назвати extract_maximum ().
Є ряд реалізацій в яких обидві основні операції виконуються в гіршому випадку за час, обмежене O (log n) - кількість збережених пар.
Як приклад черзі з пріоритетом можна розглянути список завдань працівника. Коли він закінчує одну задачу, він переходить до чергової - найбільш пріоритетним (ключ буде величиною, зворотної пріоритету) - тобто виконує операцію вилучення максимуму. Начальник додає завдання в список, вказуючи їх пріоритет, тобто виконує операцію додавання елемента.
Розширення черзі з пріоритетом Правити
На практиці інтерфейс черзі з пріоритетом нерідко розширюють іншими операціями:
- повернути мінімальний елемент без видалення з черги
- змінити пріоритет довільного елемента
- видалити довільний елемент
- злити дві черги в одну
Черга з пріоритетами може бути реалізована на основі різних структур даних.
Найпростіші (і не дуже ефективні) реалізації можуть використовувати невпорядкований або впорядкований масив. зв'язний список. підходящі для невеликих черг. При цьому обчислення можуть бути як «ледачими» (тяжкість обчислень переноситься на витяг елемента), так і ранніми (eager), коли вставка елемента складніше його вилучення. Тобто, одна з операцій може бути проведена за час O (1)
Більш ефективними є реалізації на основі купи. де обидві операції можна проводити в гіршому випадку за час O (log N)
Абстрактний тип даних (АТД) для черги з пріоритетом виходить з АТД купи перейменуванням відповідних функцій. Мінімальна (максимальне) значення знаходиться завжди на вершині гори.
Приклад на Python Правити
Стандартна бібліотека Python містить модуль heapq. який реалізує чергу з пріоритетом:
Цей приклад виведе слово «heap».