STL详解 —— priority_queue的使用与模拟实现
- priority_queue的使用
- priority_queue的介绍
- priority_queue的定义方式
- priority_queue各个接口的使用
- priority_queue的模拟实现
- 仿函数
- priority_queue的模拟实现
priority_queue的使用
priority_queue的介绍
std::priority_queue 是 C++ 标准库中的容器适配器，它提供了一种基于堆的优先级队列实现。优先级队列是一种特殊的队列，其中的元素按照一定的优先级顺序排列，而不是按照它们被插入的顺序。
在 std::priority_queue 中，插入元素时会根据元素的值自动进行排序，最大（或最小）的元素总是位于队列的顶部。对顶部元素的访问和弹出操作都是 O(1) 的时间复杂度，而插入操作则是 O(log n) 的时间复杂度。
priority_queue的定义方式
注意看 std::priority_queue的模板参数，总共三个参数
-
T (Type)：这是最重要的模板参数，它表示存储在优先队列中的元素类型。例如，如果要创建一个存储整数的优先队列，则可以指定 int 作为 T 的类型。
-
Container：这是一个可选的模板参数，用于指定底层容器的类型，默认情况下是 std::vector。优先队列使用底层容器来存储元素，因此可以通过指定不同的容器类型来影响优先队列的性能和行为。
-
Compare：这也是一个可选的模板参数，用于指定比较函数的类型，默认情况下是 std::less。比较函数用于确定优先队列中元素的顺序，例如 std::less 表示使用 < 运算符来进行比较，创建一个最大堆；而 std::greater 则表示使用 > 运算符来进行比较，创建一个最小堆。
因为后两个参数给了缺省值，所以在定义的时候可以只传一个参数，但注意，缺省只能从右往左缺，不能从左往右缺。
std::priority_queue<int> pq; // 创建一个存储整数的最大堆
std::priority_queue<int, std::deque<int>> pq; // 创建一个存储整数的最大堆，使用双端队列作为底层容器
std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // 创建一个存储整数的最小堆
std::priority_queue<int, std::deque<int>, std::greater<int>> pq; // 创建一个存储整数的最小堆，使用双端队列作为底层容器，使用 std::greater 进行元素比较
priority_queue各个接口的使用
priority_queue的各个成员函数及其功能如下:
| 成员函数 | 功能 |
|---|---|
| push | 插入元素到队尾 (并排序) |
| pop | 弹出队头元素 (堆顶元素) |
| top | 访问队头元素 (堆顶元素) |
| size | 获取队列中有效元素个数 |
| empty | 判断队列是否为空 |
| swap | 交换两个队列的内容 |
下面分别演示一个建最大堆和建最小堆的priority_queue。
#include <iostream>
#include <queue>
int main() {
// 创建一个最大堆，默认使用 std::less 比较函数
std::priority_queue<int> maxHeap;
// 插入元素
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(5);
// 访问顶部元素
std::cout << "Top of maxHeap: " << maxHeap.top() << std::endl; // 输出: 5
// 弹出顶部元素
maxHeap.pop();
// 创建一个最小堆，使用 std::greater 比较函数
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
// 插入元素
minHeap.push(3);
minHeap.push(1);
minHeap.push(5);
// 访问顶部元素
std::cout << "Top of minHeap: " << minHeap.top() << std::endl; // 输出: 1
return 0;
}
priority_queue的模拟实现
仿函数
首先先了解一下仿函数：
仿函数（Functor） 是 C++ 中的一个概念，它是一种行为类似函数的对象，可以像函数一样被调用。仿函数实际上是一个类对象，重载了函数调用运算符 operator()。
因为priority_queue是基于堆实现的，在堆排中我们每次的插入元素都需要进行向上调整，每次pop都需要向下调整，所以在下面的模拟实现中我们使用仿函数来进行改写我们之前写过的向上调整和向下调整。
示例仿函数
#include <iostream>
// 定义一个仿函数类
class MyFunctor {
public:
// 重载函数调用运算符
int operator()(int x, int y) {
return x + y;
}
};
int main() {
MyFunctor myFunctor; // 创建一个仿函数对象
// 使用仿函数对象进行函数调用
int result = myFunctor(3, 4);
std::cout << "Result: " << result << std::endl; // 输出: 7
return 0;
}
priority_queue的模拟实现
我们在之前写过数据结构|堆及其堆排序，我们之前实现的AdjustUp 与 AdjustDown 分别如下：
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if ((a[child] < a[child + 1]) && child + 1 < size)
{
child++;
}
if (a[parent] < a[child])
{
Swap(&a[child], &a[parent]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
这里我们因为确定元素的类型是int，所以直接使用了 < >来进行比较大小。
下面我们使用仿函数改写：
因为仿函数是一个类对象，所以我们分别使用less 和 greater 来表示不同功能的仿函数类。
template<class T>
class less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
由参数可知：使用类模板 class Compare 仿函数比普通函数显得更加灵活，完美的诠释了泛型编程。
后期让想改变排序方式只用更改模板参数即可。
template<class T, class Container = std::vector<T>,class Compare = less<T>>
void adjust_up(size_t child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void adjust_down(size_t parent)
{
Compare com;
size_t 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]))
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
示例：
//qq::priority_queue<int,vector<int>,greater<int>> pq;
qq::priority_queue<int> pq; //隐式定义，默认是less，建大堆
pq.push(1);
pq.push(3);
pq.push(2);
pq.push(8);
pq.push(5);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
//8 5 3 2 1
显示调用，建小堆。
qq::priority_queue<int,vector<int>,greater<int>> pq;
//qq::priority_queue<int> pq;
pq.push(1);
pq.push(3);
pq.push(2);
pq.push(8);
pq.push(5);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
//1 2 3 5 8
建立的是大堆（大顶堆），那么每次从堆中取出的都是当前堆中的最大值，再进行pop，向下调整。因此，如果你从大堆中依次取出所有元素并打印，那么打印出来的序列将是降序的。
同理 建立的是小堆（小顶堆），那么每次从堆中取出的都是当前堆中的最小值，再进行pop，向下调整。因此，如果你从小堆中依次取出所有元素并打印，那么打印出来的序列将是升序的。
namespace qq
{
template<class T>
class less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T, class Container = std::vector<T>,class Compare = less<T>>
class priority_queue
{
public:
void adjust_up(size_t child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void adjust_down(size_t parent)
{
Compare com;
size_t 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]))
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
const T& top()
{
return _con[0];
}
private:
Container _con;
};
}
