STL：优先队列

C++中的优先队列（priority queue）是一种用于维护一组元素构成的集合的容器适配器，其中每个元素都有一个优先级。添加到优先队列中的元素将按照其优先级排序，优先级最高的元素将首先被移除。优先队列通常使用堆（heap）数据结构来实现，以支持高效的元素插入和移除操作。

在C++标准库中，优先队列通过priority_queue模板类提供，该模板类定义在头文件<queue>中。

基本用法

#include <iostream>
#include <queue>

int main() {
    // 创建一个int类型的优先队列，默认使用std::less<int>，
    // 即最大值优先
    std::priority_queue<int> pq;

    // 向优先队列中插入元素
    pq.push(30);
    pq.push(10);
    pq.push(20);
    pq.push(5);

    // 遍历优先队列（这不是最好的方法，因为会改变队列内容）
    while (!pq.empty()) {
        // 访问队头元素
        std::cout << pq.top() << " ";
        // 移除队头元素
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

输出结果将是：

30 20 10 5 

自定义优先级

你可以通过定义自己的比较函数或者重载operator<来实现自定义类型的优先级排序。比如，使用[[结构体]]并自定义优先级规则：

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

struct MyStruct {
    int value;
    // 自定义比较函数
    bool operator<(const MyStruct& other) const {
        // 这里定义的是最小值优先
        return value > other.value;
    }
};

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

    // 向优先队列中插入元素
    pq.push({10});
    pq.push({30});
    pq.push({20});
    pq.push({5});

    // 遍历优先队列
    while (!pq.empty()) {
        std::cout << pq.top().value << " ";
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

输出结果将是：

5 10 20 30 

在这个例子中，自定义的比较运算符让我们能够实现最小值优先的排序逻辑。注意，当使用自定义类型时，必须确保提供用于比较元素的机制，要么通过重载operator<，要么通过提供自定义的比较函数对象。