【C++/STL】优先级队列的介绍与模拟实现&&仿函数
【C++/STL】优先级队列的介绍与模拟实现&&仿函数
🚀前言
点击跳转到文章【C++/STL】stack/queue的使用及底层剖析&&双端队列&&容器适配器
前面我们已经学习了list容器的相关知识，本文主要介绍STL中另外两种重要的结构，stack和queue。但是在STL中这两者并没有划分在容器范围内，而是将其称为容器适配器。
注意：使用优先级队列要包含头文件 < queue >。
一、优先级队列
✨1、什么是优先级队列
优先级队列是一种特殊的队列，其中的元素都被赋予了优先级。元素的优先级决定了它们在队列中的顺序。在优先级队列中，元素按照优先级从高到低的顺序出队列。
优先级队列可以通过不同的数据结构来实现，常用的有二叉堆、二叉搜索树和斐波那契堆等。
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。
✨2、优先级队列使用
函数声明 | 接口说明 |
|---|---|
priority_queue()/priority_queue(first,last) | 构造一个优先级队列 |
empty( ) | 检测优先级队列是否为空，是返回true，否则返回false |
top( ) | 返回优先级队列中最大(最小元素)，即堆顶元素 |
push(x) | 在优先级队列中插入元素x |
pop() | 删除优先级队列中最大(最小)元素，即堆顶元素 |
测试代码如下：
这里的建堆一般有两种方式： (1) 一种是一个一个push进vector容器再进行向上调整建堆 (2) 另一种是直接用迭代器区间构造直接建堆(推荐用这种)。
#include<iostream>
using namespace std;
#include<vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{
// 默认情况下，创建的是大堆
vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };
priority_queue<int> q1;
//使用范围for入队列
for (auto e : v)q1.push(e);
while (!q1.empty())
{
cout << q1.top() << " ";
q1.pop();
}
cout << endl;
// 建小堆，将第三个模板参数换成greater比较方式
//迭代器区间构造，直接建堆
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
while (!q2.empty())
{
cout << q2.top() << " ";
q2.pop();
}
}注意：优先级队列默认的大堆，降序排列，如果要升序，就要换仿函数。下图中第三个模板参数就是传仿函数。
使用算法库里的 less 和 greater 算法，需要包含头文件< functional >
二、仿函数
✨1，什么是仿函数
仿函数也叫函数对象，是一个重载了 运算符operator() 的类或结构体，可以使得类的对象像函数一样使用，通过重载函数调用运算符，仿函数可以实现自定义的操作行为。
✨2，仿函数的简单示例
operator()并没有参数的个数和返回值，所以使用是十分灵活的。
💞样例1：
// 仿函数/函数对象：重载了oparator（）的类，类的对象可以像函数一样使用
// operator()特点，参数个数和返回值根据需求确定，不固定，很多样化
class Func
{
public:
//void operator()() //()函数调用参数列表括号运算
//{
// cout << "Func调用" << endl;
//}
void operator()(int n = 1) //有参
{
while (n--)
{
cout << "Func调用" << endl;
}
}
};
int main()
{
Func f1;
f1();//使得对象像函数一样使用
f1.operator()(); //显示调用
cout << endl;
Func f2;
f2(3);
return 0;
}
💞样例2：模拟实现求平方的功能
// 定义仿函数类
struct Square {
int operator()(int a) const
{
return a * a;
}
};
int main()
{
Square square; // 创建仿函数对象
int result = square(5); // 调用仿函数
return 0;
}通过仿函数，我们可以实现更灵活和自定义的操作行为，并且可以与STL算法等标准库函数配合使用，提高代码的可读性和可维护性。
三、优先级队列模拟实现
优先级队列模拟实现和队列类似，所不同的是每次插入数据后都会使用算法将队列中的数据调整为一个堆，每次删除也是删除堆顶元素，然后将剩余的元素再次调整为一个堆，这样每次堆顶的元素就是所有数据中优先级最高的那一个了，
#pragma once
#include<vector>
#include<functional>
namespace qian
{
template<class T>
struct less
{
bool operator()(const T& left, const T& right)
{
return left < right;
}
};
template<class T>
struct greater
{
bool operator()(const T& left, const T& right)
{
return left > right;
}
};
template <class T, class Container = std::vector<T>, class Compare = less<T> >
class priority_queue
{
public:
priority_queue() //= default;
:c()
{}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
//:c(first,last) //和下面的一样，都是将数据输入c中
{
while (first != last)
{
c.push_back(*first);
++first;
}
for (int i = c.size() / 2 - 1; i >= 0; i--) {
AdjustDown(i);
}
}
bool empty() const
{
return c.empty();
}
size_t size() const
{
return c.size();
}
const T& top() const
{
return c[0]; //上下一样的
//return c.front();
}
void AdjustUp(int child)
{
int parent = (child - 1) >> 1;
while (child > 0)
{
if (comp(c[parent], c[child]))
{
std::swap(c[parent], c[child]);
child = parent;
parent = (child - 1) >> 1;
}
else break;
}
}
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child < c.size())
{
if (child + 1 < c.size() && comp(c[child], c[child + 1]))
{
++child;
}
if (comp(c[parent], c[child]))
{
std::swap(c[parent], c[child]);
parent = child;
child = parent * 2 + 1;
}
else break;
}
}
void push(const T& x)
{
c.push_back(x);
AdjustUp(c.size() - 1);
}
void pop()
{
if (empty()) return;
std::swap(c.front(), c.back());
c.pop_back();
AdjustDown(0);
}
private:
Container c;
Compare comp;
};
};测试代码如下：
void test_priority_queue()
{
int a[] = { 2,1,7,6,0,4,3,9,8,5 };
// 默认是大堆
qian::priority_queue<int> q1(a, a+sizeof(a)/sizeof(int));
// 小堆
qian::priority_queue<int, vector<int>, qian::greater<int>> q2(a, a + sizeof(a) / sizeof(int));
cout << "大堆：" << " ";
while (!q1.empty())
{
cout << q1.top() << " ";
q1.pop();
}
cout << endl;
cout << "小堆：" << " ";
while (!q2.empty())
{
cout << q2.top() << " ";
q2.pop();
}
cout << endl;
}腾讯云开发者
