C++ 容器类 <priority_queue>

在 C++ 中，<priority_queue> 是标准模板库（STL）的一部分，用于实现优先队列。

优先队列是一种特殊的队列，它允许我们快速访问队列中具有最高（或最低）优先级的元素。

在 C++ 中，priority_queue 默认是一个最大堆，这意味着队列的顶部元素总是具有最大的值。

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 的简单实例，我们将创建一个最大堆，并展示如何添加元素和获取队列顶部的元素。

实例

#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。