В этой статье мы обсудим еще один специализированный контейнер в 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: возвращает размер приоритетной очереди, т. е. количество элементов в приоритетной очереди.
Вот пример программу, которая демонстрирует использование этих функций/операций:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <queue> using namespace std; void displaypq(priority_queue <int> pri_queue) { priority_queue <int> pq = pri_queue; while (!pq.empty()) { cout << '\t' << pq.top(); pq.pop(); } cout << '\n'; } int main () { priority_queue <int> mypq; mypq.push(1); mypq.push(3); mypq.push(60); cout<<"\nPriority queue after inserting value 60: "; displaypq(mypq); mypq.push(5); cout<<"\n\nPriority queue after inserting value 5: "; displaypq(mypq); mypq.push(10); cout << "\nThe priority queue mypq is : "; displaypq(mypq); cout << "\nmypq.size() : " << mypq.size(); cout << "\nmypq.top() : " << mypq.top(); cout << "\nmypq.pop() : "; mypq.pop(); displaypq(mypq); return 0; } |
Вывод данных:
| 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.
Снова вставляем еще одно значение 10, и по-прежнему вершина очереди с приоритетом равна 60. Это связано с тем, что при отправке элементов порядок или приоритет элементов сохраняется таким, что наибольший элемент всегда находится наверху.
Итог
Вот и все, что мы хотели вам рассказать в этой статье о приоритетной очереди в STL и ее реализации. Из нашей следующей статьи вы узнаете о картах в STL.
С Уважением, МониторБанк