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

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

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

#include <iostream>
#include <queue>

int main() {
    // 创建一个最大堆
    std::priority_queue<int> 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<int>，然后向其中添加了一些整数。由于 priority_queue 是一个最大堆，所以队列顶部的元素总是最大的。因此，当我们输出堆中的元素时，它们是按照从大到小的顺序排列的。

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

#include <iostream>
#include <queue>

int main() {
    // 创建一个最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> 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<int, std::vector<int>, std::greater<int>>，其中 std::greater<int> 是一个比较函数，它会导致 priority_queue 成为一个最小堆。因此，当我们输出堆中的元素时，它们是按照从小到大的顺序排列的。

0 赞

0 踩