Пріоритетні черги
Пріоритетна чергу (англ. Priority queue) - це абстрактна структура даних на зразок стека або черги, де у кожного елемента є пріоритет. Елемент з більш високим пріоритетом знаходиться перед елементом з більш низьким пріоритетом. Якщо у елементів однакові пріоритети, вони розташовуються в залежності від своєї позиції в черзі. Зазвичай пріоритетні черги реалізуються за допомогою куп (англ. Heap).
[Ред] Операції
Пріоритетні черги підтримують такі операції:
- або - пошук елемента з найбільшим пріоритетом,
- або - вставка нового елемента,
- або - витягти елемент з найбільшим пріоритетом,
- або - видалити елемент з найбільшим пріоритетом,
- або - оновити значення елемента,
- - об'єднання двох пріоритетних черг, зберігаючи оригінальні черзі,
- - об'єднання двох пріоритетних черг, руйнуючи оригінальні черзі,
- - розбити пріорітную чергу на дві частини.
[Ред] Реалізації
[Ред] Наївна
Як наївною реалізації ми можемо взяти звичайний список і при додаванні нового елемента класти його в кінець, а при запиті елемента з максимальним пріоритетом проходити по всьому списку. Тоді операція буде виконуватися за, а чи за.
[Ред] Звичайна
Для кращої продуктивності пріоритетні черги реалізують за допомогою куп, що дозволяє виконувати операції вставки і видалення за. Використання спеціальних куп, таких як Фібоначчієва купа і спарена купа, дозволяє ще більше поліпшити асимптотику деякий операцій.