Черга з пріоритетом

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Черги ми зустрічаємо на кожному кроці. Насамперед в суспільстві, чи в війсковій сфері, чи в магазині.

Черга з пріорітетами (англ. priority queue) — це структура даних, що призначена для обслуговування множини S, з кожним елементом якої пов'язано певне значення, що зветься ключем (англ. key). Черга з пріорітетами може бути неспадною або незростаючою. В незростаючій черзі з пріорітетами підтримуються такі операції:

  • Операція Insert(S,x) вставляє елемент x в множину S.
  • Операція Maximum(S) повертає елемент множини S з найбільшим ключем.
  • Операція Extract_Max повертає елемент з найбільшим ключем, видаляючи його при цьому з множини S.
  • Операція Change_Key(S,x,k) змінює значення ключа для елемента x на k.

Реалізація[ред.ред. код]

Черга з пріорітетами може бути реалізована на різних структурах даних. В залежності від обраної структури змінюється ефективність виконання операцій з чергою. Найбільш часто вживаними є масиви і купи.

Див. також[ред.ред. код]

Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.