C++：priority_queue优先队列

---

前言

今天我们一起来学习优先级队列~~~<(￣︶￣)↗[GO!]

---

一、优先级队列概念及用法

1.1 优先级队列概念

优先队列是一种特殊的容器适配器，主要依赖堆的结构来保证元素按照特定的顺序进行操作。它的核心功能是确保队列的第一个元素总是最大或最小的元素，具体取决于堆的类型（大顶堆或小顶堆）。

---

功能	说明
容器适配器	优先队列是通过封装标准容器类（如vector或deque）实现的，作为底层数据存储。默认情况下使用vector。
类似堆的结构	优先队列与堆相似，支持随时插入元素，并且只能访问位于顶部的最大（或最小）元素。
算法支持	内部通过自动调用堆算法，如make_heap、push_heap和pop_heap，保持队列的堆结构。
随机访问迭代器	容器类应支持随机访问迭代器，如vector和deque，以便操作元素。
元素访问与修改	提供empty()、size()、top()等函数来操作和访问容器中的元素，元素总是从容器的“顶部”弹出。

---

常用接口与方法

方法	功能说明
priority_queue()	构造一个空的优先队列。
empty()	检测优先队列是否为空，空则返回true，否则返回false。
size()	返回优先队列中的元素个数。
top()	返回优先队列中最大的元素，即堆顶元素。
push(x)	向优先队列中插入元素x，并重新调整堆结构。
pop()	删除并移除优先队列中的最大元素，即堆顶元素。

---

优先队列通常使用vector作为底层存储结构，借助堆算法将vector中的元素构造成堆的形式。对于需要频繁使用堆的场景，优先队列是一个非常高效且方便的选择。注意，默认情况下优先队列是大顶堆，即top()返回的是当前最大的元素。

---

1.2 优先级队列的使用

1.2.1 对于内置类型

大根堆的使用

priority_queue<int> q;
// 默认是大根堆，这里其实省略了三个模板参数，写完整是这样的
// <优先级队列类型, 底层容器类型, 比较方式> 变量名;
// priority_queue<int, vector<int>, less<int>> q;

• 优先级队列模板参数：
  • int: 队列中存储的数据类型。
  • vector<int>: 底层容器类型，优先队列默认使用vector来存储数据。
  • less<int>: 仿函数，用于定义优先队列的排序方式，默认是less<int>，表示大根堆（最大元素位于堆顶）。

在这里，priority_queue<int>实际上等价于priority_queue<int, vector<int>, less<int>>，即默认情况下优先队列是一个大根堆，也就是每次弹出最大值。

q.push(2);
q.push(3);
q.push(4);
q.push(1);

• 通过push()方法向优先队列中插入元素，队列会根据大根堆的规则自动调整顺序。插入顺序是2, 3, 4, 1。

while (!q.empty()) {cout << q.top() << " ";q.pop();
}

• q.top()：返回堆顶元素（当前队列中的最大值）。
• q.pop()：移除堆顶元素，并重新调整堆结构。
• 通过while循环依次输出并弹出堆顶元素，直到队列为空，输出顺序应该为4 3 2 1。

---

创建小根堆

#include // greater算法的头文件

priority_queue<int, vector<int>, greater<int>> q2;
// 如果要建小根堆，也就是升序，要更改最后一个模板参数仿函数，也就是改变比较的方式

• 这里创建了一个小根堆，不同之处在于使用了greater<int>作为仿函数。
  • greater<int>：与less<int>相反，表示升序排列，即最小元素位于堆顶。

q2.push(2);
q2.push(3);
q2.push(4);
q2.push(1);

• 同样地，通过push()方法插入元素2, 3, 4, 1，此时优先队列会自动构造成小根堆。

while (!q2.empty()) {cout << q2.top() << " ";q2.pop();
}

• 通过while循环依次输出并弹出堆顶元素，直到队列为空，输出顺序应该为1 2 3 4。

---

总结

• 大根堆：默认情况下，priority_queue使用less<int>作为仿函数，即构建大根堆，每次弹出的是最大值。
• 小根堆：通过指定greater<int>作为仿函数，可以构建小根堆，优先队列会自动将最小元素置于堆顶。

这里用deque也可以，不过我们在调整建堆是需要大量的随机访问，deque这方面是比较不行的，因此推荐适配器用vector就可以了。

---

这里还可以用迭代器区间来构造优先级队列。

void test_priority_queue02()
{vector<int> v = { 1, 3, 5 ,2 ,9 };priority_queue<int> q(v.begin(), v.end());while (!q.empty()){cout << q.top() << " ";q.pop();}cout << endl;
}

---

1.2.2 对于自定义类型

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

---

我们建议再自定义类型的内部进行operator<以及operator>，如果遇到实在无法再类内重载这些的情况，比如我传进来的日期类是一对指针，可以用一下的方法操作。

priority_queue<Date*, vector<Date*>, LessDate<Date*>> q;

• priority_queue<Date*, vector<Date*>, LessDate<Date*>>：构造了一个存储Date*类型的优先队列，并使用LessDate仿函数来进行排序。

使用自定义仿函数来处理指针类型（如Date*）的优先队列排序。默认情况下，priority_queue无法直接比较指针类型，因此需要通过自定义的仿函数LessDate来实现指针的解引用与比较。

template<class T>
class LessDate {
public:bool operator()(const Date* pd1, const Date* pd2) const {// 解引用指针并比较Date对象return *pd1 < *pd2;}
};

• LessDate类：这是一个仿函数，用于比较Date*类型的指针，内部通过解引用指针来比较Date对象的大小。
• 重载operator()：定义了比较逻辑，仿函数在优先队列中用于排序。

---

二、小试牛刀

数组中的第K个最大元素

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> q(nums.begin(), nums.end());for (int i = 0; i < k - 1; i++) q.pop();return q.top();}
};

---

三、优先级队列模拟实现

3.1 优先队列模板参数与成员变量

通过上面的使用我们可以发现，优先队列需要三个模板参数

class T //类型, class Container = vector //适配器
class compare = less//仿函数用于建堆调整比较

而它的成员变量自然就是这个适配器

template<class T, class Container = vector<T>, class compare = less<T>>
class priority_queue
{
public:private:Container _con;
};

---

3.2 构造相关

3.2.1 默认构造

• 默认构造，对于自定义类型，会去调_con的构造函数

priority_queue() {}

3.2.2 迭代器构造

template<class Iterator>
priority_queue(Iterator first, Iterator last) {while (first != last) {_con.push_back(*first);++first;}// 向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) {AdjustDown(i);}
}

建堆主逻辑

• 通过迭代器范围[first, last)将元素添加到底层容器_con中。每个元素都被依次插入到容器中。
• 在所有元素都插入后，接下来需要将这些元素调整为堆结构。通过对非叶子节点进行向下调整（调用AdjustDown），从最后一个非叶子节点开始，依次调整直到根节点。

向下调整

• 向下调整的主要逻辑在AdjustDown函数中实现。其主要目标是保持堆的性质（大根堆），具体步骤如下：
  • 从父节点开始，计算其左子节点的位置。
  • 比较父节点与子节点（及其兄弟节点）的值，找到更大的子节点。
  • 如果父节点小于最大子节点，则交换二者，并继续向下调整。
  • 直到满足堆的性质（即父节点大于或等于子节点）为止。

时间复杂度分析

• 建堆的时间复杂度：在构造函数中，插入元素的时间复杂度为O(n)，因为每个元素都需要被添加到底层容器中。
• 向下调整的时间复杂度：AdjustDown的时间复杂度为O(log n)，每次调用会最多经过树的高度（log n）进行比较和交换。由于我们需要从每个非叶子节点向下调整，整体建堆的复杂度为O(n)。

---

private://向下调整建堆void AdjustDown(int parent){int child = parent * 2 + 1;while (child < _con.size()){// 我们要排大根堆，降序排列，因此要找孩子中大的那一个if (child + 1 < _con.size() && _con[child] < _con[child + 1])child++;if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}}public://默认构造，对于自定义类型，会去调_con的构造函数priority_queue() {}//支持迭代器//迭代器也要写成模板template<class Iterator>priority_queue(Iterator first, Iterator last){while (first != last){_con.push_back(*first);++first;}//向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}

---

3.2.3 使用仿函数优化比较，实现大根堆与小根堆切换

在前面的代码中，我们直接将比较的方法写死了。

如果我们要实现小根堆呢？要重新再写一个函数吗？

答案是不用，我们可以使用一个仿函数，重新定义比较，传什么仿函数就用什么比较。

这里要注意的是，因为我们仿函数代表的仅仅是一种<或>，因此我们再写的时候要把符号关系搞成一致，像这样：

//向下调整建堆
void AdjustDown(int parent)
{//仿函数定义一个对象出来，用它来替换比较Compare com;int child = parent * 2 + 1;while (child < _con.size()){// 我们要排大根堆，降序排列，因此要找孩子中大的那一个if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))child++;if (com(_con[parent] , _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}

---

3.3 其他功能实现

3.3.1 push函数

void push(const T& x) {_con.push_back(x);AdjustUp(_con.size() - 1);
}

• 功能：将新元素x插入到优先队列中。
• 过程：
  1. 首先将元素x添加到容器_con的尾部。
  2. 然后调用AdjustUp函数，从新插入元素的位置向上调整，确保堆的性质被保持（大根堆）。

3.3.2 pop函数

void pop() {swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);
}

• 功能：删除优先队列中优先级最高的元素（堆顶元素）。
• 过程：
  1. 先将堆顶元素（即_con[0]）与堆尾元素交换。
  2. 删除堆尾元素。
  3. 通过调用AdjustDown函数，从堆顶开始向下调整，保持堆的性质。

3.3.3 top、size和empty函数

• top：返回堆顶元素，即优先队列中优先级最高的元素。
• size：返回优先队列中元素的数量。
• empty：检查优先队列是否为空。

---

向上调整 (AdjustUp)

//向上调整
void AdjustUp(int child)
{Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}

• 功能：调整刚插入的元素，使堆满足大根堆性质。
• 过程：
  1. 计算当前元素的父节点位置。
  2. 在while循环中，如果子节点的值大于父节点的值，则进行交换。
  3. 更新child和parent的值，继续向上调整，直到不再需要交换或达到根节点。

---

四、仿函数

4.1 仿函数概念

仿函数（Functor）是一个重载了 operator() 的类或结构体，能够像函数一样被调用。它们常用于需要自定义比较、处理或操作的数据结构和算法中，比如在 STL 容器、算法中作为参数传递。

仿函数的优势在于：

• 可以持有状态：仿函数的对象可以保存数据，允许使用构造函数初始化。
• 语义明确：通过命名类，能够清晰表达意图。

以下是一个简单的仿函数例子:

#include <iostream>
using namespace std;// 定义一个仿函数类
class Compare {
public:// 重载运算符()bool operator()(int a, int b) const {return a < b; // 返回true表示a小于b}
};int main() {Compare compare;int x = 5, y = 10;// 使用仿函数进行比较if (compare(x, y)) {cout << x << " is less than " << y << endl;} else {cout << x << " is not less than " << y << endl;}return 0;
}

输出

5 is less than 10

Compare 类实现了一个仿函数，通过重载 operator() 来比较两个整数。通过创建 Compare 的对象并调用它，就可以像使用普通函数一样进行比较。

---

4.2 优先队列中的模拟实现

//仿函数模拟实现/函数对象
template<class T>
class Less
{
public:bool operator() (const T& a, const T& b){return a < b;}
};template<class T>
class Greater
{
public:bool operator() (const T& a, const T& b){return a > b;}
};

---

总代码实现

以下是优先队列中大根堆和小根堆的对应关系，以及根节点的最大和最小属性：

堆类型	比较方式	仿函数	根节点
大根堆	>	std::less<T>	最大
小根堆	<	std::greater<T>	最小

#pragma once
#include<vector>namespace jyf
{//仿函数模拟实现/函数对象template<class T>class Less{public:bool operator() (const T& a, const T& b){return a < b;}};template<class T>class Greater{public:bool operator() (const T& a, const T& b){return a > b;}};template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{private://向下调整void AdjustDown(int parent){//仿函数定义一个对象出来，用它来替换比较Compare com;int child = parent * 2 + 1;while (child < _con.size()){// 我们要排大根堆，降序排列，因此要找孩子中大的那一个if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))child++;if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}}//向上调整void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}}public://默认构造，对于自定义类型，会去调_con的构造函数priority_queue() {}//支持迭代器//迭代器也要写成模板template<class Iterator>priority_queue(Iterator first, Iterator last){while (first != last){_con.push_back(*first);++first;}//向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void push(const T& x){//先放到堆尾_con.push_back(x);//进行向上调整AdjustUp(_con.size() - 1);}void pop(){//先交换第一个和最后一个swap(_con[0], _con[_con.size() - 1]);//删除堆尾_con.pop_back();//向下调整AdjustDown(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_priority_queue1(){// 默认是大堆 -- less//priority_queue<int> pq;// 仿函数控制实现小堆priority_queue<int, vector<int>, Greater<int>> pq;pq.push(3);pq.push(5);pq.push(1);pq.push(4);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}
}

---

到这里就结束啦，谢谢大家!!!💕💕💕😍😍😍○( ＾皿＾)っHiahiahia…