Что такое структура данных priority_queue?

Sobes Copilot

Получайте ответы в реальном времени

Ответ от нейросети

sobes.tech AI

priority_queue — адаптер контейнера из стандартной библиотеки C++, который предоставляет функциональность очереди с приоритетами. Элементы извлекаются в порядке их приоритета (по умолчанию, наибольший элемент имеет наивысший приоритет). По сути, это обертка над другим контейнером (по умолчанию std::vector), которая использует алгоритмы кучи (std::make_heap, std::push_heap, std::pop_heap) для поддержания структуры кучи внутри базового контейнера.

Ключевые особенности:

Приоритет: Элементы извлекаются согласно их приоритету. По умолчанию используется std::less для определения приоритета, что означает наибольший элемент считается имеющим наивысший приоритет (макс-куча). Можно изменить порядок, предоставив другой компаратор, например, std::greater для мин-кучи.
Адаптер: priority_queue не является самостоятельным контейнером, а адаптирует другой базовый контейнер (обычно std::vector, но может быть и другой, например std::deque), предоставляя интерфейс очереди с приоритетами.
Куча: Внутренне реализована с использованием кучи, что обеспечивает логарифмическую сложность для операций вставки и извлечения.
Неупорядоченный доступ: Не предоставляет произвольного доступа к элементам. Доступны только операции вставки (push), извлечения элемента с наивысшим приоритетом (pop) и просмотра элемента с наивысшим приоритетом (top).

Основные операции:

Операция	Описание	Сложность (в среднем/худшем случае)
`push`	Вставляет элемент с заданным приоритетом.	O(log N)
`pop`	Удаляет элемент с наивысшим приоритетом.	O(log N)
`top`	Возвращает константную ссылку на элемент с наивысшим приоритетом.	O(1)
`empty`	Проверяет, пуста ли очередь.	O(1)
`size`	Получает количество элементов в очереди.	O(1)

Пример использования:

#include <queue>
#include <vector>
#include <iostream>
#include <functional> // для std::greater

int main() {
    // Макс-куча (по умолчанию)
    std::priority_queue<int> max_pq;
    max_pq.push(10);
    max_pq.push(30);
    max_pq.push(20);

    std::cout << "Элементы макс-кучи (top): ";
    while (!max_pq.empty()) {
        std::cout << max_pq.top() << " ";
        max_pq.pop();
    }
    std::cout << std::endl;

    // Мин-куча (используя std::greater<int>)
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(10);
    min_pq.push(30);
    min_pq.push(20);

    std::cout << "Элементы мин-кучи (top): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

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