引言

std::priority_queue 是 C++ 标准库中一个重要的容器适配器，它以堆数据结构为基础，实现了优先队列的功能。与普通队列不同，优先队列按照元素的优先级进行排序，每次取出的元素都是当前队列中优先级最高的元素。这种特性使得 std::priority_queue 在许多场景下都有着广泛的应用。

定义与头文件

std::priority_queue 定义在 <queue> 头文件中，其模板定义如下：

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

模板参数

T：代表存储在优先队列中的元素类型。无论是内置类型（如 int、double 等）还是自定义类型，都可以作为 T 的实例。
Container：用于存储元素的底层容器，默认是 std::vector<T>。除了 std::vector，std::deque<T> 也是常见的选择。该容器需要支持随机访问（例如 operator[]）、push_back() 和 pop_back() 操作。std::vector 由于其连续的内存布局，通常在大多数情况下性能更优，利于缓存命中；而 std::deque 在频繁插入和删除元素时可能更具优势。
Compare：比较函数对象类型，用于定义元素之间的比较规则。这部分决定了 priority_queue 中元素的排序方式。

排序设定

默认排序（大顶堆）：默认情况下，Compare 为 std::less<typename Container::value_type>。std::less 是 C++ 标准库中的一个函数对象，重载了 () 运算符，实现了小于比较（a < b）。对于内置类型，如 int，这意味着 priority_queue 会按照降序排列元素，形成大顶堆，即堆顶元素是队列中的最大元素。例如：

std::priority_queue<int> maxHeap;
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(4);
// 此时 maxHeap.top() 将返回 4

小顶堆排序：若要实现小顶堆（即队首元素是最小元素），可以将 Compare 设为 std::greater<typename Container::value_type>。std::greater 同样是标准库中的函数对象，重载的 () 运算符实现大于比较（a > b）。例如：

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(3);
minHeap.push(1);
minHeap.push(4);
// 此时 minHeap.top() 将返回 1

自定义类型的排序：当 priority_queue 存储自定义类型时，需要定义合适的比较规则。

重载比较运算符：对于自定义类 MyClass，可以重载 < 运算符来定义比较逻辑。例如：

class MyClass {
public:
    int value;
    MyClass(int v) : value(v) {}
    bool operator<(const MyClass& other) const {
        return value > other.value; // 按 value 从大到小排序
    }
};
std::priority_queue<MyClass> pq;
pq.push(MyClass(3));
pq.push(MyClass(1));
pq.push(MyClass(4));
// 此时 pq.top() 将返回 value 为 4 的 MyClass 对象

自定义比较函数对象：也可以通过定义一个结构体或类作为比较函数对象，并在其中重载 `()` 运算符。例如：

class MyClass {
public:
    int value;
    MyClass(int v) : value(v) {}
};
struct MyClassCompare {
    bool operator()(const MyClass& a, const MyClass& b) const {
        return a.value < b.value; // 按 value 从小到大排序
    }
};
std::priority_queue<MyClass, std::vector<MyClass>, MyClassCompare> pq;
pq.push(MyClass(3));
pq.push(MyClass(1));
pq.push(MyClass(4));
// 此时 pq.top() 将返回 value 为 1 的 MyClass 对象

常见操作

构造函数

默认构造函数：创建一个空的优先队列。例如：

std::priority_queue<int> pq1;

通过初始化列表构造：使用初始化列表来初始化优先队列。例如：

std::priority_queue<int> pq2({3, 1, 4, 1, 5, 9});

插入与删除操作

push()：将元素插入到优先队列中，并重新调整堆结构以保持优先级顺序。其时间复杂度为 $O(\log n)$，其中 $n$ 是优先队列中的元素个数。例如：

pq1.push(10);

pop()：移除并丢弃优先队列中优先级最高的元素（队首元素），然后重新调整堆结构。时间复杂度同样为 $O(\log n)$。例如：

pq1.pop();

访问操作

top()：返回优先队列中优先级最高的元素（队首元素），但不删除它。时间复杂度为 O(1)。例如：

int topElement = pq1.top();

其他操作

size()：返回优先队列中元素的个数，时间复杂度为 O(1)。例如：

size_t size = pq1.size();

empty()：检查优先队列是否为空，时间复杂度为 O(1)。例如：

bool isEmpty = pq1.empty();

示例代码

#include <iostream>
#include <queue>

int main() {
    // 创建一个默认的大顶堆优先队列
    std::priority_queue<int> maxHeap;
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(4);
    maxHeap.push(1);
    maxHeap.push(5);
    maxHeap.push(9);

    std::cout << "大顶堆元素（从大到小）: ";
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    std::cout << std::endl;

    // 创建一个小顶堆优先队列
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(1);
    minHeap.push(5);
    minHeap.push(9);

    std::cout << "小顶堆元素（从小到大）: ";
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }
    std::cout << std::endl;

    // 自定义类型大顶堆示例
    class MyClass {
    public:
        int value;
        MyClass(int v) : value(v) {}
        bool operator<(const MyClass& other) const {
            return value > other.value;
        }
    };
    std::priority_queue<MyClass> myMaxHeap;
    myMaxHeap.push(MyClass(3));
    myMaxHeap.push(MyClass(1));
    myMaxHeap.push(MyClass(4));
    std::cout << "自定义类型大顶堆元素（从大到小）: ";
    while (!myMaxHeap.empty()) {
        std::cout << myMaxHeap.top().value << " ";
        myMaxHeap.pop();
    }
    std::cout << std::endl;

    // 自定义类型小顶堆示例
    struct MyClassCompare {
        bool operator()(const MyClass& a, const MyClass& b) const {
            return a.value < b.value;
        }
    };
    std::priority_queue<MyClass, std::vector<MyClass>, MyClassCompare> myMinHeap;
    myMinHeap.push(MyClass(3));
    myMinHeap.push(MyClass(1));
    myMinHeap.push(MyClass(4));
    std::cout << "自定义类型小顶堆元素（从小到大）: ";
    while (!myMinHeap.empty()) {
        std::cout << myMinHeap.top().value << " ";
        myMinHeap.pop();
    }
    std::cout << std::endl;

    return 0;
}

应用场景

任务调度

在操作系统的任务调度中，每个任务可能被赋予不同的优先级。priority_queue 可以用于按照任务优先级对任务进行排序，确保高优先级任务优先执行，从而优化系统资源的分配和利用效率。

图算法

例如在 Dijkstra 算法中，该算法用于计算图中节点间的最短路径。priority_queue 被用来存储待处理的节点，根据节点到源点的距离作为优先级，每次取出距离源点最近的节点进行扩展，以此逐步找到最短路径。

数据筛选

从大量数据中筛选出前 $k$ 个最大（或最小）的元素。比如，在学生成绩管理系统中，找出成绩排名前 k 的学生，priority_queue 能够高效地完成这类数据筛选任务。

注意事项

元素类型要求

存储在 priority_queue 中的元素类型必须支持比较操作。对于自定义类型，除了重载比较运算符外，提供自定义比较函数对象时，要确保其逻辑清晰、正确，以保证优先队列能按照预期的优先级规则进行排序。

底层容器选择

虽然默认使用 std::vector 作为底层容器，但开发者应根据实际应用场景来选择合适的底层容器。如果插入和删除操作非常频繁，std::deque 可能是更好的选择；而在大多数通用场景下，std::vector 凭借其内存布局优势能提供较好的性能。

稳定性

std::priority_queue 是不稳定的，即相同优先级的元素在队列中的相对顺序是不确定的。如果在某些应用中需要保持相同优先级元素的顺序，就需要考虑使用其他数据结构，或者自行实现稳定的优先队列。

通过合理运用 std::priority_queue，开发者能够方便、高效地实现各种需要优先级排序的功能，显著提高程序的效率和可读性。无论是在系统级编程还是算法实现中，std::priority_queue 都是一个强大且实用的工具。

杰人编程网

C++ 优先队列priority_queue全面解析

引言