Контейнерные классы C++<priority_queue>

В C++,<priority_queue>Является частью Standard Template Library (STL) и используется для реализации очередей с приоритетом.

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

В C++,priority_queueПо умолчанию это max-heap, что означает, что верхний элемент очереди всегда имеет наибольшее значение.

priority_queueЯвляется адаптером контейнера, который предоставляет операции с кучей для базового контейнера. Он не предоставляет итераторы и не поддерживает произвольный доступ.

Синтаксис

Ниже приведеныpriority_queueБазовый синтаксис:

#include <queue>

// 声明一个整型优先队列
priority_queue<int> pq;

// 声明一个自定义类型的优先队列，需要提供比较函数
struct compare {
    bool operator()(int a, int b) {
        return a > b; // 这里定义了最小堆
    }
};
priority_queue<int, vector<int>, compare> pq_min;

Общие операции

  • empty(): Проверить, пуста ли очередь.
  • size(): Вернуть количество элементов в очереди.
  • top(): Вернуть элемент на вершине очереди (не удаляя его).
  • push(): Добавить элемент в очередь.
  • pop(): Удалить элемент на вершине очереди.

Пример

Ниже приведён пример использованияpriority_queueПростой пример с ним: мы создадим max-heap и покажем, как добавлять элементы и получать элемент на вершине очереди.

Пример

#include <iostream>
#include <queue>

int main() {
    // Создать целочисленную очередь с приоритетом
    std::priority_queue<int> pq;

    // Добавить элементы в приоритетную очередь
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    // Вывести элементы очереди
    std::cout << "Элементы в очереди:" << std::endl;
    while (!pq.empty()) {
        std::cout << pq.top() << std::endl;
        pq.pop();
    }

    return 0;
}

Результат вывода:

队列中的元素：
50
30
20
10

Пользовательский приоритет

Если вам нужна минимальная куча, её можно реализовать, настроив функцию сравнения:

Пример

#include <iostream>
#include <queue>
#include <vector>

struct compare {
    bool operator()(int a, int b) {
        return a > b; // Определить минимальную кучу
    }
};

int main() {
    // Создать очередь с приоритетом пользовательского типа с использованием минимальной кучи
    std::priority_queue<int, std::vector<int>, compare> pq_min;

    // Добавить элементы в приоритетную очередь
    pq_min.push(30);
    pq_min.push(10);
    pq_min.push(50);
    pq_min.push(20);

    // Вывести элементы очереди
    std::cout << "Элементы в минимальной куче:" << std::endl;
    while (!pq_min.empty()) {
        std::cout << pq_min.top() << std::endl;
        pq_min.pop();
    }

    return 0;
}

Результат вывода:

最小堆中的元素：
10
20
30
50

<priority_queue>Это очень полезный контейнер в C++ STL, особенно подходящий для сценариев, где требуется быстрый доступ к элементу с наибольшим или наименьшим приоритетом. Настраивая функцию сравнения, мы можем легко реализовать максимальную или минимальную кучу. Я надеюсь, что эта статья поможет начинающим лучше понять и использовать его.priority_queue。

Другие расширения