Черга з пріоритетами
Матеріал з Вікіпедії — вільної енциклопедії.
Черга з пріорітетами (англ. priority queue) — це структура даних, що призначена для обслуговування множини S, з кожним елементом якої пов'язано певне значення, що зветься ключем (англ. key). Черга з пріорітетами може бути неспадною або незростаючою. В незростаючій черзі з пріорітетами підтримуються наступні операції:
- Операція Insert(S,x) вставляє елемент x в множину S.
- Операція Maximum(S) повертає елемент множини S з найбільшим ключем.
- Операція Extract_Max повертає елемент з найбільшим ключем, видаляючи його при цьому з множини S.
- Операція Change_Key(S,x,k) змінює значення ключа для елемента x, шляхом заміни його ключем зі значенням k.
[ред.] Реалізація
Черга з пріорітетами може бути реалізована на різних структурах даних. В залежності від обраної структури змінюється ефективність виконання операцій з чергою. Найбільш часто вживаними є масиви і купи.

