济南最好的网站建设公司,设计平台app,网站做标签页,软件开发net教程免费前言#xff1a;在前面我们学习了栈和队列的使用与模拟实现#xff0c;今天我们来进一步的学习优先级队列使用与模拟实现 #x1f496; 博主CSDN主页:卫卫卫的个人主页 #x1f49e; #x1f449; 专栏分类:高质量#xff23;学习 #x1f448; #x1f4af;代码仓库:卫…前言在前面我们学习了栈和队列的使用与模拟实现今天我们来进一步的学习优先级队列使用与模拟实现 博主CSDN主页:卫卫卫的个人主页 专栏分类:高质量学习 代码仓库:卫卫周大胖的学习日记 关注博主和博主一起学习!一起努力 目录标题 什么是优先级队列优先级的队列常见功能的使用方式什么是仿函数 优先级队列的底层实现(适配器版本)优先级队列的基本框架push()将元素入队列pop()删除队列中优先级最高的元素top()获取并返回队列中优先级最高的元素size()获取并返回队列大小empty()判断队列是否为空 整体代码 什么是优先级队列
C中的优先级队列是一种特殊的数据结构它类似于队列但是元素按照优先级进行排序。在优先级队列中元素的插入被赋予了一个优先级值具有较高优先级的元素将排在较低优先级的元素之前(用大白话讲就是你队列中的元素按照某种要求进行了对应的排序)。
C中的优先级队列通常使用堆heap作为底层实现可以是最小堆或最大堆。最小堆意味着优先级值较小的元素具有较高的优先级而最大堆则相反。
优先级队列的主要操作是插入和删除最高优先级的元素。在C中可以使用std::priority_queue模板类来实现优先级队列。该模板类提供了一些成员函数如push()、pop()和top()等用于插入、删除和获取最高优先级的元素。 优先级的队列常见功能的使用方式
1.插入元素使用push()函数向优先级队列插入元素(调用前需要导入头文件queue)
int main()
{priority_queueint s1;//创建一个对象s1.push(10);//入队列且队列中的元素会默认按照降序进行排序s1.push(20);s1.push(0);s1.push(9);s1.push(120);return 0;
}删除最高优先级元素使用pop()函数删除优先级队列中的最高优先级元素(可以理解成删除队列中排序过后的队头的元素)。
int main()
{priority_queueint s1;s1.push(10);//入队列s1.push(120);s1.pop();//删除队头的元素return 0;
}获取最高优先级元素使用top()函数获取优先级队列中的最高优先级元素通俗的理解获取队列排序过后的队头元素。
int main()
{priority_queueint s1;s1.push(10);//入队列s1.push(9);s1.push(120);s1.pop();//出队列auto num s1.top();//获取队列的队头的元素cout num endl;return 0;
}//运行结果10获取队列中的元素数量使用size()函数获取优先级队列中的元素数量。
int main()
{priority_queueint s1;s1.push(10);//入队列cout s1.size() endl;//输出队列中元素的个数return 0;
}判断队列是否为空使用empty()函数判断优先级队列是否为空。
int main()
{priority_queueint s1;s1.push(10);s1.push(20);s1.push(0);s1.push(9);s1.push(120);auto num s1.top();cout num endl;cout s1.size() endl;if (!s1.empty())//判断队列是否有元素{cout 队列中有元素 endl;}else cout 队列中没有元素 endl;return 0;
}需要注意的是std::priority_queue默认以降序排序即最大元素具有最高优先级。如果希望以升序排序则可以使用自定义的比较函数或者使用std::greater作为模板参数
// 使用自定义的比较函数,greater即默认升序的排序方式,也可以调用自己写的排序方式
std::priority_queueint, std::vectorint, std::greaterint pq;// 或者使用std::greater模板参数
std::priority_queueint, std::vectorint, std::greater pq; 什么是仿函数
C中的仿函数是一个类或者结构体实现了函数调用操作符(operator())的重载。通过重载函数调用操作符可以使得仿函数对象像函数一样被调用。仿函数常用于算法中用于实现特定的操作或者运算。它可以接受一个或多个参数并返回一个结果。通过仿函数可以实现函数对象的状态的维护以及在算法中对元素进行处理的定制化操作。 例子
template class T
class less//通过类来判断他的大小
{
public:operator() (const T x, const T y){return x y;}
};template class T
class greater//同理
{
public:operator() (const T x, const T y){return x y;}
};int main()
{int num1 10, num2 20,num3 30,num4 50;lessint s1;greaterint s2;if (s1(num1, num2))//s1()就类似与之前的一个函数的样子我们调用s1这个对象即可完成你想要指定的操作{cout num1 num2 endl;}if (s2(num4, num3))//同理你调用s2也可以类似于函数的感觉去完成你想要指定完成的操作{cout num4 num3 endl;}return 0;
}
优先级队列的底层实现(适配器版本)
前言:这里我们需要先知道刚刚我们使用了那些功能这里方便我们对其进行模拟实现。 基本操作 1、push()将元素入队列。【将元素入队列并且让其按照升序或者降序进行某种方式进行排序】
2、pop()删除队列中优先级最高的元素。【队首出队列并且依然要保持队列的完整性】
3、top()获取并返回队列中优先级最高的元素。
4、size()获取并返回队列大小。【返回值为 unsigned intsize_t类型】
5、empty()判断队列是否为空。【返回值为bool类型。队列为空返回true不空返回false】 优先级队列的基本框架
namespace bit
{templateclass Tclass less//通过类来实现仿函数来帮助我们实现运算符重载达到控制升序降序的目的{public:bool operator()(const T x, const T y){return x y;}};templateclass Tclass greater//通过仿函数来帮助我们实现升序和降序{public:bool operator()(const T x, const T y){return x y;}};template class T, class Container vectorT, class Compare lessT//默认是大堆,借助适配器帮助实现class priority_queue//基本类{public:private:Container _con;//调用适配器}
}push()将元素入队列
代码思路我们的适配器默认调用的是vector因为他内部的接口可以调用尾插同理我们这里直接调用尾插的函数即可但是我们提到过这个是一个优先级队列优先级队列的底层就是一个,那么我们对堆插入元素的时候在数据结构讲过我们需要对其进行调整否则这个堆就会失去他原有的完整性如果对堆这块内容不太熟悉的小伙伴可以去看看我之前的博客堆的模拟实现
void push(const T x)//入队列
{_con.push_back(x);//需要保证队列里面的优先级的顺序因此我们需要对其进行向上调整adjust_up(_con.size() - 1);//当前的元素个数减一就是当前孩子结点下标然后将他向上调整即可完成插入
}//向上调整
void adjust_up(size_t child)//插入的是孩子看孩子是否比父亲还大比父亲还大就交换,且是默认大堆
{Compare com;int parent (child - 1) / 2;//父亲结点的下标while (child 0){//巧妙的利用仿函数对其进行默认的降序进行排序也可以通过传great进行升序排序if (com(_con[parent], _con[child]))//比父亲大就交换{swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;//孩子不比父亲大说明就是当前的位置}}
}pop()删除队列中优先级最高的元素
代码思路在之前讲解堆的时候我们知道要想删除堆顶的元素我们通常的做法是将堆顶的元素和尾元素进行交换然后在删除此时堆尾部的元素进行删除然后在将交换后的堆顶的元素向下调整保持堆的完整性因此我们在优先级队列中需要用到同样的做法将队首和队尾的元素进行交换然后删除队尾的元素然后向下调整即可。
void pop()//队头出队列
{swap(_con[0], _con[_con.size() - 1]);//将堆的底部元素和堆顶的交换然后删除堆底部元素就完成了队头出队列_con.pop_back();//删除堆顶元素adjust_down(0);//向下调整交换过后的堆即依然保持堆的完整性
}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]))//父亲比孩子小就向下调整{swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}
}top()获取并返回队列中优先级最高的元素
代码思路我们知道优先级队列的底层就是个堆队首的那个元素就是堆顶的元素因此直接返回下标为0的首元素即可。
const T top()//获取队首元素
{return _con[0];
}size()获取并返回队列大小
代码思路这里我们直接调用容器中的函数即可
size_t size()//查看队列中元素的个数
{return _con.size();
}empty()判断队列是否为空
代码思路同理调用容器中的函数即可。
bool empty()//判断是否为空,依然玩适配器的那套玩法
{return _con.empty();
}整体代码
#include iostream
#includevector
#includeassert.h
using namespace std;namespace bit
{templateclass Tclass less{public:bool operator()(const T x, const T y){return x y;}};templateclass Tclass greater{public:bool operator()(const T x, const T y){return x y;}};template class T, class Container vectorT, class Compare lessT//默认是大堆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]))//比父亲大就交换{swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;//孩子不比父亲大说明就是当前的位置}}}void push(const T x)//入队列{_con.push_back(x);adjust_up(_con.size() - 1);//vector的元素个数减一就是当前孩子结点下标然后将他向上调整即可完成插入}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]))//父亲比孩子小就向下调整{swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}void pop()//队头出队列{swap(_con[0], _con[_con.size() - 1]);//将堆的底部元素和堆顶的交换然后删除堆底部元素就完成了队头出队列_con.pop_back();//删除堆顶元素adjust_down(0);//向下调整交换过后的堆即依然保持堆的完整性}bool empty()//判断是否为空,依然玩适配器的那套玩法{return _con.empty();}size_t size()//查看队列中元素的个数{return _con.size();}const T top()//获取队首元素{return _con[0];}private:Container _con;};void test1(){bit::priority_queueint, vectorint, bit::greaterint pq;pq.push(2);pq.push(1);pq.push(4);pq.push(3);pq.push(7);pq.push(8);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;}void test2(){priority_queueint pq;//默认大堆pq.push(2);pq.push(1);pq.push(4);pq.push(3);pq.push(7);pq.push(8);while (pq.size()){cout pq.top() ;pq.pop();}cout endl;}
}emplate class T
class less
{
public:operator() (const T x, const T y){return x y;}
};template class T
class greater
{
public:operator() (const T x, const T y){return x y;}
};int main()
{int num1 10, num2 20,num3 30,num4 50;lessint s1;greaterint s2;if (s1(num1, num2)){cout num1 num2 endl;}if (s2(num4, num3)){cout num4 num3 endl;}return 0;
}//int main()
//{
// //bit::test1();
// //bit::test2();
// return 0;
//}好啦今天的内容就到这里啦下期内容预告C中的模板大全解. 结语前段时间博主又又又去忙学校的事情和一些比赛啥的这段时间会猛猛干的。 ️ 这里祝各位接下来的每一天好运连连
