Очереди с приоритетами. Операции над очередями с приоритетами. - EcsFlash/DataTypes GitHub Wiki

Определения

Очередь с приоритетом представляем из себя абстрактный тип данных, особенностью которого является механика добавления и удаления элементов. Предполагается, что для каждого элемента можно вычислить его приоритет — типо действительное число или что-то что можно между собой сравнить(например воинские звания), по которому и будет определяться местоположение элемента в данной структуре данных.

Суть

Очередь с приоритетами нужна для того, чтобы в нее класть какие то неупорядоченные элементы, а доставать - по возрастанию/убыванию приоритета, то есть в зависимости от реализации, элемент с наименьшим/наибольшим приоритетом ВСЕГДА будет "в начале" очереди, порядок элементов с одинаковым приоритетом нас не интересует, а элементы с наибольшим/наименьшим приоритетом выйдут последними.

Для примера: в "живой" очереди к врачу стоят несколько человек, приоритет которых одинаков. Их порядок нас не интересует. Приходит в эту очередь человек с талоном, его приоритет больше, чем у остальных - значит он становится в начало очереди, а не в конец и следовательно попадет в кабинет врача он раньше, чем остальные.

Для очереди с приоритетами доступны(в нашем случае) следующие операции:

  1. создание пустой очереди
  2. удаление(очистка)
  3. проверка на пустоту
  4. вставка
  5. удаление из очереди
  6. просмотр первого элемента

Несмотря на название "очередь" данная структура данных не реализует принцип FIFO, и в самом тривиальном понимании является списком, упорядоченным по приоритету.