Приоритетная очередь в STL

Priority_queueВ этой статье мы обсудим еще один специализированный контейнер в STL, а именно приоритетную очередь.

Очередь с приоритетом — это приемщик контейнера в STL. Очередь с приоритетом — это контейнер, в котором элементы расположены в неубывающем порядке, так что первый элемент всегда является самым большим элементом в очереди.

В отличие от обычной очереди, которая выталкивает и извлекает элемент в соответствии с порядком FIFO, у приоритетной очереди элементы находятся в неубывающем порядке и имеют приоритет (фиксированный порядок) для каждого элемента.

Очередь приоритетов можно рассматривать так же, как структуру данных «max heap» в C++.

Общий синтаксис приоритетной очереди:

priority_queue <objectType> queue_name;

Итак, если мы хотим определить приоритетную очередь типа int, мы можем определить ее следующим образом:

priority_queue<int> mypqueue;

Операции с priority_queue

Давайте посмотрим на операции, поддерживаемые priority_queue:

  • Push: вставляет элемент в приоритетную очередь. При вставке элементов приоритет элементов сохраняется.
  • Pop: удаляет самый верхний элемент из очереди приоритетов.
  • Top: возвращает самый верхний элемент в очереди приоритетов, т. е. самый высокий элемент в очереди приоритетов.
  • Empty: проверяет, пуста ли приоритетная очередь.
  • Size: возвращает размер приоритетной очереди, т. е. количество элементов в приоритетной очереди.

Читать также:  Книга «Управление электронными устройствами на C++»

Вот пример программу, которая демонстрирует использование этих функций/операций:

Вывод данных:

Priority queue after inserting value 60:         60             3              1
Priority queue after inserting value 5:            60             5              3              1
The priority queue mypq is :      60       10       5               3              1
mypq.size() : 5
mypq.top() : 60
mypq.pop() : 10              5             3                 1

Пожалуйста, внимательно проверьте вывод, чтобы понять работу приоритетной очереди. Сначала мы вводим значения 1,3,60, как показано в первой строке вывода. Затем мы помещаем значение 5 в очередь приоритетов. После этого отображается приоритетная очередь. Обратите внимание, что хотя значение 5 помещается после 60, вершиной очереди приоритетов все еще является 60.

Читать также:  Преобразование типов в C++

Снова вставляем еще одно значение 10, и по-прежнему вершина очереди с приоритетом равна 60. Это связано с тем, что при отправке элементов порядок или приоритет элементов сохраняется таким, что наибольший элемент всегда находится наверху.

Итог

Вот и все, что мы хотели вам рассказать в этой статье о приоритетной очереди в STL и ее реализации. Из нашей следующей статьи вы узнаете о картах в STL.

С Уважением, МониторБанк

Добавить комментарий