Що таке черга з пріоритетом?

Черга з пріоритетом (priority queue) - це структура даних, де кожен елемент має пріоритет, і під час видалення вибирається не перший доданий, а найбільш пріоритетний елемент.

#Як це працює

• Кожен елемент зберігається як пара: (значення, пріоритет).
• Під час додавання елемент поміщається в чергу.
• Під час видалення (dequeue) вилучається елемент з найвищим пріоритетом, а не той, що був доданий раніше.

#Приклад використання

У лікарні пацієнти приходять у порядку черги, але лікар приймає спочатку тих, у кого стан важчий - пріоритет вищий.

#Реалізація

• Найчастіше - через купу (heap), зазвичай мінімальну або максимальну.
  • Додавання (insert) - O(log n),
  • Вилучення елемента з найвищим пріоритетом - O(log n),
  • Отримання максимуму/мінімуму без видалення - O(1).

Таким чином, черга з пріоритетом - це черга, де порядок визначається не часом надходження, а значенням пріоритету.