priority_queue学习笔记

priority_queue 是 C++ STL 中的一个容器，是一个优先级队列。它类似于队列，但是不同于队列的是，每个元素都有一个优先级，优先级最高的元素先出队列。在 priority_queue 中，元素的出队顺序是按照元素的优先级从高到低排序的。

priority_queue 基于堆（heap）实现。在 STL 中，堆是指一类数据结构，它可以被看作是一棵完全二叉树。堆分为两种类型：最大堆和最小堆。最大堆的每个节点的值都大于或等于其子节点的值，最小堆则相反。在 priority_queue 中，默认情况下是最大堆。

使用 priority_queue 的第一步是包含头文件 #include 。然后可以使用如下语句定义一个 priority_queue：

priority_queue<int> q; // 定义一个默认的最大堆

在定义时可以指定自定义的排序规则：

struct cmp {
    bool operator() (int a, int b) {
        return a > b; // 最小堆
    }
};

priority_queue<int, vector<int>, cmp> q; // 定义一个最小堆

上述代码中，定义了一个自定义的排序规则 cmp，它是一个函数对象。其中，operator() 是函数调用运算符，用于比较两个元素的大小。最后一个参数表示使用自定义的排序规则。

priority_queue 中最重要的操作是 push() 和 pop()。push() 用于插入一个元素到队列中，pop() 用于从队列中删除一个元素。

priority_queue<int> q;
q.push(2);
q.push(1);
q.push(3);
cout << q.top() << endl; // 输出 3
q.pop();
cout << q.top() << endl; // 输出 2

除此之外，priority_queue 还有其他常用的操作，如 size()、empty()、swap() 等。

最后需要注意的是，priority_queue 并不支持随机访问元素，如果需要随机访问元素，建议使用 vector、deque 或其他容器。此外，由于是基于堆实现的，因此空间复杂度较高。