`std::priority_queue` — это контейнер-адаптер в C++, который предоставляет функциональность приоритетной очереди. Приоритетная очередь — это структура данных, которая позволяет вставлять элементы и извлекать элемент с наивысшим приоритетом. В случае `std::priority_queue`, элемент с наивысшим приоритетом — это элемент с наибольшим значением по умолчанию, что означает, что это очередь с максимальным приоритетом.

Основные характеристики:

1. Автоматическая сортировка: Элементы внутри приоритетной очереди автоматически сортируются таким образом, что элемент с наивысшим приоритетом всегда находится на вершине.
2. Доступ только к элементу с наивысшим приоритетом: Вы можете получить доступ только к элементу с наивысшим приоритетом (то есть к самому большому элементу, если не указано иное).
3. Основана на куче (heap): Реализация `std::priority_queue` основана на двоичной куче, что обеспечивает эффективное выполнение основных операций.

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

• push(value): Вставляет элемент в приоритетную очередь.
• pop(): Удаляет элемент с наивысшим приоритетом.
• top(): Возвращает ссылку на элемент с наивысшим приоритетом.
• empty(): Проверяет, пуста ли приоритетная очередь.
• size(): Возвращает количество элементов в приоритетной очереди.

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

```cpp
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(20);
    pq.push(5);
    pq.push(15);

    std::cout << "Top element (should be 20): " << pq.top() << std::endl;

    pq.pop(); // Удаляет элемент 20

    std::cout << "Top element after pop (should be 15): " << pq.top() << std::endl;

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}
```

Объяснение кода:

1. Создание приоритетной очереди: `std::priority_queue<int> pq;` создаёт приоритетную очередь для целых чисел.
2. Вставка элементов: Вставляются элементы 10, 20, 5 и 15.
3. Получение и удаление элемента с наивысшим приоритетом:

• `pq.top()` возвращает элемент 20, так как он имеет наивысший приоритет.
• `pq.pop()` удаляет элемент 20.
• Следующий вызов `pq.top()` возвращает элемент 15.

4. Вывод всех элементов: В цикле выводятся и удаляются все элементы, начиная с самого большого.

Кастомизация приоритетной очереди:

По умолчанию, `std::priority_queue` работает как максимальная куча. Можно изменить её поведение на минимальную кучу, передав компаратор. Например, используя `std::greater`:

```cpp
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);
    minHeap.push(15);

    std::cout << "Top element (should be 5): " << minHeap.top() << std::endl;

    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }

    return 0;
}
```

`std::priority_queue` — это структура данных, которая позволяет эффективно вставлять элементы и извлекать элемент с наивысшим приоритетом, используя внутреннюю реализацию на основе кучи. По умолчанию элементы сортируются в порядке убывания, но можно изменить поведение с помощью пользовательского компаратора.

May 24, 2024, easyoffer