C++ PriorityQueue 如何实现优先级排序

在 C++ 中，priority_queue 是一个容器适配器，它提供了优先级队列的数据结构。priority_queue 默认是一个最大堆（max heap），也就是说，队列顶部的元素总是最大的。如果你想要实现最小堆（min heap），你可以传递一个比较函数给 priority_queue 的构造函数。

下面是一个使用 priority_queue 实现优先级排序的例子：

#include 
#include 

int main() {
    // 创建一个最大堆
    std::priority_queue pq;

    // 向堆中添加元素
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    pq.push(9);
    pq.push(2);
    pq.push(6);
    pq.push(5);
    pq.push(3);
    pq.push(5);

    // 输出堆中的元素
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

在这个例子中，我们创建了一个 priority_queue，然后向其中添加了一些整数。由于 priority_queue 是一个最大堆，所以队列顶部的元素总是最大的。因此，当我们输出堆中的元素时，它们是按照从大到小的顺序排列的。

如果你想要实现最小堆，你可以传递一个比较函数给 priority_queue 的构造函数，如下所示：

#include 
#include 

int main() {
    // 创建一个最小堆
    std::priority_queue, std::greater> pq;

    // 向堆中添加元素
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    pq.push(9);
    pq.push(2);
    pq.push(6);
    pq.push(5);
    pq.push(3);
    pq.push(5);

    // 输出堆中的元素
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

在这个例子中，我们创建了一个 priority_queue, std::greater>，其中 std::greater 是一个比较函数，它会导致 priority_queue 成为一个最小堆。因此，当我们输出堆中的元素时，它们是按照从小到大的顺序排列的。