В C++ приоритетная очередь — это адаптер контейнера, который предоставляет интерфейс, подобный очереди, но позволяет обрабатывать элементы на основе их приоритетов. По умолчанию элементы в очереди с приоритетом упорядочиваются на основе функции сравнения или оператора, при этом элемент с наивысшим приоритетом всегда находится впереди. В этой статье основное внимание уделяется созданию и работе с приоритетной очередью для хранения пар частот и элементов, что может быть полезно в различных сценариях, например при поиске наиболее часто встречающихся элементов в коллекции.
Создание приоритетной очереди пар:
Чтобы создать приоритетную очередь для хранения пар частот и элементов, необходимо определить тип элементов, хранящихся в очереди, как pair<int, int>. Эта пара представляет частоту и значения элементов. Первый элемент в паре будет представлять частоту, а второй элемент будет представлять фактическое значение элемента.
#include <queue> #include <utility> // Creating a priority queue of pairs std::priority_queue<std::pair<int, int>> pq;
Приведенный выше код объявляет приоритетную очередь pq, в которой будут храниться пары частот и элементов. std::pair<int, int> указывает тип каждого элемента в очереди приоритетов.
Вставка элементов в приоритетную очередь:
Чтобы вставить элементы в приоритетную очередь, вы можете использовать функцию push и указать пару частот и элементов в качестве аргументов.
pq.push(std::make_pair(frequency, element));
Функция push добавляет пару в очередь приоритетов в соответствии с указанным порядком приоритетов. Элемент с наибольшей частотой будет помещен в начало очереди.
Доступ к элементам и их удаление:
Чтобы получить доступ к верхнему элементу очереди с приоритетом, вы можете использовать функцию top, которая возвращает ссылку на пару с наивысшим приоритетом.
std::pair<int, int> topPair = pq.top(); int frequency = topPair.first; int element = topPair.second;
Функция top извлекает верхний элемент приоритетной очереди. В этом случае он извлекает пару с наибольшей частотой и присваивает значения частоты и элемента отдельным переменным.
Чтобы удалить верхний элемент из очереди с приоритетом, вы можете использовать функцию pop.
pq.pop();
Функция pop удаляет верхний элемент из очереди приоритетов, делая следующий элемент с наивысшим приоритетом новым верхним.
Заключение.
Создание очереди с приоритетами для хранения пар частот и элементов в C++ может быть полезно для решения различных задач, связанных с определением приоритетов элементов на основе частоты. Поняв, как создавать очередь пар приоритетов и работать с ней, вы сможете эффективно обрабатывать и извлекать элементы с наивысшим приоритетом.
