前言
和stack与queue一样,priority_queue也是一种容器适配器。
他的本质其实是堆,作优先级队列的底层需要能够通过随机迭代器访问,所以他的底层是可以由vector和queue实例化,默认情况下priority_queue默认是用vector作为底层实例化,此外我们还可以特指定deque作为他的底层进行实例化。
需要支持随即迭代器,是因为要始终维持堆,优先级队列的本质就是堆。容器适配器通过在需要时自动调用算法函数make_heap,push_heap,pop_heap来始终维持堆。
priority_queue默认是大堆。
priority_queue的使用
priority_queue定义方式
优先级队列有三个模板参数,第一个是元素种类,第二个是用来构造优先级队列的底层容器种类,第三个是构建的方式(大堆还是小堆)。
//这种是不指定底层容器和构造方式的构建,默认底层是vector,构建大堆
priority_queue<int> pq;
//这种指定了底层容器和构造方式,我这里设置的底层是deque<int>,构建的是小堆
priority_queue<int,deque<int>,greater<int>> pq1;
//我们这里如果要是想要选择构建大堆还是小堆的时候,就只能必须把底层容器的类型也给了
//这是设置缺省参数时的规定,这里不赘述
priority_queue的接口介绍
成员函数 | 功能 |
---|---|
push | 元素入队,通过push_heap函数使其移向堆中适当的位置 |
pop | 元素出队,通过pop_heap函数使剩下的元素维持住堆的形式 |
top | 获取堆顶元素(优先级最大或最小的元素) |
size | 返回队中有效数据个数 |
empty | 判断是否为空 |
swap | 交换两个优先级队列中的内容 |
示例代码:
#include<queue>
#include<iostream>
using namespace std;
void test1()
{
priority_queue<int> pq;
pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
priority_queue<int, vector<int>, greater<int>>pq2;
pq2.push(1);
pq2.push(2);
pq2.push(3);
pq2.push(4);
while (!pq2.empty())
{
cout << pq2.top() << " ";
pq2.pop();
}
cout << endl;
}
int main()
{
test1();
return 0;
}
如何支持自定义类型使用priority_queue
1.使用仿函数
仿函数就是重载实现 ( ) ,使 ( ) 有实际的意义,因为使用的时候特别像函数调用,所以取名叫仿函数。例如我们有下面的一个类student,我们根据他的成绩_student从小到大进行排序:
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
class student
{
public:
student(size_t id, size_t grade) :
_id(id),
_grade(grade)
{}
size_t getId() const
{
return _id;
}
size_t getGrade() const
{
return _grade;
}
private:
size_t _id;
size_t _grade;
};
//先创建一个结构体cmp,struct访问权限是public
//里面构造仿函数,我们这里要实现从小到大排序,就要创建小堆,也就是greater的内容
struct cmp
{
bool operator()(student& s1,student& s2) {
return s1.getGrade() > s2.getGrade();
}
};
void test1()
{
student s1(1,100);
student s2(2,80);
student s3(3,90);
student s4(4,60);
vector<student>s;
s.push_back(s1);
s.push_back(s2);
s.push_back(s3);
s.push_back(s4);
priority_queue<student, vector<student>, cmp> pq;
for (auto& e : s)
{
pq.push(e);
}
while (!pq.empty())
{
student s = pq.top();
cout << s.getId() << endl;
pq.pop();
}
}
int main()
{
test1();
return 0;
}
2.通过运算符重载来实现自定义实现比较函数
当你使用 priority_queue
时,它需要一个比较函数或者比较对象来决定元素的排序。这个比较函数需要满足一定的要求,特别是它需要能够处理 const
对象。因为priority_queue底层本质上是一个堆,在我们进行插入删除的时候,需要不断调整,在我们调整的过程中是不希望元素的数值改变的。因此在底层我们的编译器只接受const修饰的元素。所以我们在进行operator>或operator<的时候,里面的参数是一定要加上const的。
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
class student
{
public:
friend bool operator>(student& s1, student& s2);
student(size_t id, size_t grade) :
_id(id),
_grade(grade)
{}
size_t getId() const
{
return _id;
}
size_t getGrade() const
{
return _grade;
}
private:
size_t _id;
size_t _grade;
};
//struct cmp
//{
// bool operator()(student& s1, student& s2) {
// return s1.getGrade() > s2.getGrade();
// }
//};
bool operator>(const student& s1,const student& s2)//这里一定要加上const,只接收const对象
{
return s1.getGrade() > s2.getGrade();
}
void test1()
{
student s1(1, 100);
student s2(2, 80);
student s3(3, 90);
student s4(4, 60);
vector<student>s;
s.push_back(s1);
s.push_back(s2);
s.push_back(s3);
s.push_back(s4);
priority_queue<student, vector<student>, greater<student>> pq;
for (auto& e : s)
{
pq.push(e);
}
while (!pq.empty())
{
student s = pq.top();
cout << s.getId() << endl;
pq.pop();
}
}
int main()
{
test1();
return 0;
}
priority_queue的模拟实现
我们前面讲过优先级队列实际就是堆结构,我们要实现它就要先学习两个堆的算法:向上调整算法和向下调整算法。我们这里以构建大堆举例:
向上调整算法
void adjustUp(vector<int>& v,int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (v[parent] < v[child])
{
swap(v[parent], v[child]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
//这里我们要构建的是一个大堆,如果儿子的值大于父亲的值就交换位置继续迭代向上迭代
向下调整算法
//堆的向下调整(大堆)
void adjustDown(vector<int>& v, int parent)
{
//child记录左右孩子中值较大的孩子的下标
int child = 2 * parent + 1;//先默认其左孩子的值较大
while (child < v.size())
{
if (child + 1 < v.size() && v[child] < v[child + 1])//右孩子存在并且右孩子比左孩子还大
{
child++;//较大的孩子改为右孩子
}
if (v[parent] < v[child])//左右孩子中较大孩子的值比父结点还大
{
//将父结点与较小的子结点交换
swap(v[child], v[parent]);
//继续向下进行调整
parent = child;
child = 2 * parent + 1;
}
else//已成堆
{
break;
}
}
}
模拟实现
模拟实现实际上就是在上面两个调整算法的基础上,设计几个接口:
namespace cyf
{
template<class T>
struct less
{
bool operator()(const T& t1, const T& t2)
{
return t1 < t2;
}
};
template<class T>
struct greater
{
bool operator()(const T& t1, const T& t2)
{
return t1 > t2;
}
};
template<class T,class Container=vector<T>,class Compare=less<int>>
class Mypriority_queue
{
public:
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child != 0)
{
if (com_(con_[parent], con_[child]))
{
swap(con_[parent], con_[child]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(int parent)
{
int child = 2 * parent + 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 = 2 * child + 1;
}
else
{
break;
}
}
}
void push(const T& val)//先尾插,再向上调整
{
con_.push_back(val);
AdjustUp(con_.size() - 1);
}
int size()
{
return con_.size();
}
//先交换第一个元素和最后一个元素,之后将换后的最后一个元素删除,之后从0向下调整
void pop()
{
swap(con_[0], con_[size() - 1]);
con_.pop_back();
AdjustDown(0);
}
T& top()//两种访问堆顶元素的top()函数
{
return con_[0];
}
const T& top() const
{
return con_[0];
}
bool empty() const
{
return con_.empty();
}
private:
Container con_;//存储容器
Compare com_; //比较方式
};
}
以上就是有关优先级队列的全部内容,希望能对大家有所帮助!