更多 C++语法知识在 C++语言学记专栏
往期 STL 容器看点：
这篇文章是关于 C++所有数据结构概览中的单独专题

顺序容器	vector	array	list	deque	forward_list
关联容器	set&multiset	map&multimap	无序关联容器	Unordered set&multiset	Unordered map&multimap
容器适配器	stack	queue	priority_queue	其他容器	string

std::priority_queue 和 stack、queue 不同，它既不是后进先出（LIFO），也不是先进先出（FIFO）。它实现的是一种**“优先级出队”**的规则：无论元素何时入队，优先级最高的元素总是最先出队。你可以把它想象成医院的急诊室：医生永远优先处理病情最危重的病人，而不是最先来的病人。

在底层，std::priority_queue 通常由一种叫做**“堆（Heap）”**的数据结构实现。

---

1. std::priority_queue 的基本使用语法

要使用 priority_queue，同样需要包含头文件 <queue>。

#include <iostream>
#include <queue> // stack, queue, priority_queue 都在这个头文件里
#include <vector>
#include <functional> // 后面讲解自定义优先级时会用到

1.1 声明和初始化

priority_queue 的声明比 stack 和 queue 要复杂一些，因为它涉及到优先级的定义。

最简单的声明（默认行为）：

// 创建一个存储 int 类型的优先队列
// 默认情况下，这是一个 "大顶堆 (Max-Heap)"
// 意味着数值越大的元素，优先级越高
std::priority_queue<int> pq;

1.2 核心成员函数

它的接口和 stack 非常相似，只是 top() 的含义不同。

函数名	功能描述
push(element)	将一个元素 element 添加到队列中，并根据优先级自动调整位置。
pop()	移除队首（即优先级最高）的元素。同样没有返回值。
top()	返回对队首（即优先级最高）元素的常量引用。只返回，不移除。
empty()	检查队列是否为空。
size()	返回队列中元素的数量。

注意：priority_queue 没有 front() 或 back() 函数，因为它只关心优先级最高的那个元素，这个元素永远在 top()。

1.3 代码示例（默认大顶堆）

#include <iostream>
#include <queue>

int main() {
    // 1. 创建一个默认的优先队列（大顶堆）
    std::priority_queue<int> pq;

    // 2. 使用 push() 添加元素
    // 每次添加后，内部都会重新排序以维持堆的结构
    std::cout << "Pushing 30, 100, 25, 40..." << std::endl;
    pq.push(30);
    pq.push(100);
    pq.push(25);
    pq.push(40);

    // 3. 使用 size() 查看元素数量
    std::cout << "Current size: " << pq.size() << std::endl; // 输出: 4

    // 4. 使用 top() 访问优先级最高的元素
    // 因为是大顶堆，所以数值最大的元素在顶部
    std::cout << "Top element (highest priority): " << pq.top() << std::endl; // 输出: 100

    // 5. 使用 pop() 移除顶部元素
    std::cout << "Popping the top element..." << std::endl;
    pq.pop(); // 100 出队

    // 再次访问顶部元素
    std::cout << "Now the top element is: " << pq.top() << std::endl; // 输出: 40

    // 6. 遍历并清空队列
    // 出队顺序总是从大到小
    std::cout << "Popping all elements: ";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl; // 输出: 40 30 25

    return 0;
}

---

2. 底层知识与自定义优先级

这部分是 priority_queue 最核心、最灵活的地方。

2.1 底层容器

priority_queue 也是一个容器适配器。它的模板定义如下：

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

它有三个模板参数：

1. T: 存储的元素类型。

2. Container: 用于存储元素的底层容器。

3. Compare: 用于定义元素优先级的比较函数。

默认底层容器：std::vector<T>

• 为什么是 vector？ 因为 priority_queue 的底层数据结构是堆，而堆可以非常高效地用一个数组（或 vector）来表示。vector 提供了快速的随机访问能力，这对于维持堆结构所必需的“上浮（sift-up）”和“下沉（sift-down）”操作至关重要。

• std::deque 也可以作为底层容器，但 std::list 不行，因为它不支持快速的随机访问。

2.2 比较函数与优先级

priority_queue 的行为完全由第三个模板参数 Compare 决定。

• 默认行为：Compare 的默认值是 std::less<T>。std::less 是一个函数对象（functor），less(a, b) 在 a < b时返回 true。在优先队列中，比较函数的逻辑可以理解为“如果 Compare(a, b) 为 true，那么 b 的优先级比 a 高”。

  • 所以对于 std::less<int>，当 a < b 时，b 的优先级更高。结果就是数值大的元素优先级更高，形成大顶堆。

2.3 如何创建小顶堆（Min-Heap）

如果你希望数值越小的元素优先级越高（小顶堆），你需要提供一个不同的比较函数。最简单的方法是使用标准库里的 std::greater<T>。

• 对于 std::greater<int>，当 a > b 时，greater(a, b) 为 true，这意味着 b 的优先级比 a 高。结果就是数值小的元素优先级更高，形成小顶堆。

创建小顶堆的语法：

// 模板参数的顺序：元素类型, 底层容器, 比较函数
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

min_pq.push(30);
min_pq.push(100);
min_pq.push(25);

std::cout << "Top element of min-heap: " << min_pq.top() << std::endl; // 输出: 25

2.4 对自定义类型使用优先队列

当你想在优先队列中存储自定义的结构体或类时，你有两种主流方法来定义它们的优先级。

假设我们有这样一个结构体：

struct Person {
    std::string name;
    int age;
};

方法一：重载 < 运算符

如果你只根据一种固定的规则（比如年龄越大优先级越高）来排序，可以为 Person 类重载 < 运算符。这样就可以直接使用默认的 std::priority_queue。

struct Person {
    std::string name;
    int age;

    // 重载 < 运算符。
    // a < b 意味着 b 的优先级更高。
    // 这里我们定义年龄小的人 "小于" 年龄大的人。
    // 因此，年龄大的人优先级更高。
    bool operator<(const Person& other) const {
        return this->age < other.age;
    }
};

int main() {
    std::priority_queue<Person> pq; // 使用默认的 std::less<Person>
    pq.push({"Alice", 25});
    pq.push({"Bob", 30});
    pq.push({"Charlie", 20});

    std::cout << "Highest priority person: " << pq.top().name << ", Age: " << pq.top().age << std::endl; // 输出: Bob, Age: 30
    return 0;
}

方法二：提供自定义比较函数（Functor）

这是更灵活、更推荐的方法，因为它不“污染”你的类定义，并且可以根据不同需求创建不同的优先队列。

struct Person {
    std::string name;
    int age;
};

// 自定义一个比较结构体（函数对象）
// 我们希望年龄小的人优先级更高（小顶堆）
struct ComparePersonAge {
    // a > b 时返回 true，意味着 b 的优先级比 a 高
    bool operator()(const Person& a, const Person& b) const {
        return a.age > b.age;
    }
};

int main() {
    // 明确指定所有模板参数
    std::priority_queue<Person, std::vector<Person>, ComparePersonAge> pq;

    pq.push({"Alice", 25});
    pq.push({"Bob", 30});
    pq.push({"Charlie", 20});

    std::cout << "Highest priority person: " << pq.top().name << ", Age: " << pq.top().age << std::endl; // 输出: Charlie, Age: 20
    return 0;
}

总结

• 是什么：std::priority_queue 是一个“最高优先级先出”的容器适配器。

• 怎么用：接口与 stack 几乎一样，使用 push(), pop(), top()。top() 永远指向优先级最高的元素。

• 底层是什么：通常由**堆（Heap）**实现，默认依赖 std::vector 作为底层容器，因为它支持高效的随机访问。

• 默认行为：大顶堆（Max-Heap），数值大的元素优先级高，由 std::less 定义。

• 高度可定制：通过提供不同的比较函数（如 std::greater 或自定义的 Functor），可以轻松创建小顶堆或为任何自定义对象定义复杂的优先级规则，这是 priority_queue 最强大的特性。