【C++初阶】：优先队列（仿函数）

た入场券 2024-03-17 23:47 96阅读 0赞

#### 优先队列 ####

*  一.基本使用
 *  二.模拟实现
 *  三.仿函数
 *   *  1.优先队列里的使用
     *  2.概念
     *  3.模拟

## 一.基本使用 ##

> **优先队列的底层默认是使用vector构造的，也就是使用数组模拟（二叉树）堆。并且默认是按大堆存放数据（也就是父节点>子节点，左节点>右节点）。**

![在这里插入图片描述][1510754bde4c4966aaa65ad509504a70.png]

> **优先队列的成员函数不多，常用的就是empty,size,top,pop,push。**

![在这里插入图片描述][3e393ab4b16644fe9206a3af7af1f154.png]

*简单使用*

> **首先优先队列常使用区间初始化和无参初始化。**

![在这里插入图片描述][c89e59b41fe24c67b3f7778f0563570c.png]

> **可以使用push插入数据，注意因为优先队列是使用数组模拟堆，所以不能直接遍历。只能通过不断访问顶部数据，再不断弹出顶部数据进行间接遍历。**

![在这里插入图片描述][cbf4fb48fc334fa582afd007f815cdf4.png]

![在这里插入图片描述][f0cc706d0a9049a6993daa562ca0722c.png]

## 二.模拟实现 ##

> **这里使用了模板参数（template<class T,class Container=vector>），一共有两个参数，第一个T用来适配不同类型的数据（例如int,string或者自定义类型）,第二个参数默认是vector，也就是底层默认是用vector实现优先队列，当然也可以使用list等等（这里与库里保持一致）。**

#include<vector>
    
    namespace mine
    {
        
    	template<class T,class Container=vector<T>>
    	class priority_queue
    	{
        
    	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[child], _con[parent]);
    					parent = child;
    					child = parent * 2 + 1;
    				}
    				else
    				{
        
    					break;
    				}	
    			}
    		}
    
    		//向上调整
    		void AdjustUp(int child)
    		{
        
    			int parent = (child - 1) / 2;
    			while (child > 0)
    			{
        
    				if (_con[parent] <_con[child])
    				{
        
    					swap(_con[child], _con[parent]);
    					child = parent;
    					parent = (child - 1) / 2;
    				}
    				else
    				{
        
    					break;
    				}
    			}
    		}
    	public:
    		//无参构造
    		priority_queue()
    		{
        }
    		//区间构造
    		template<class InputLterater>
    		priority_queue(InputLterater first,InputLterater last)
    		{
        
    			while (first != last)
    			{
        
    				_con.push_back(*first);
    				first++;
    			}
    
    			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
    			{
        
    				AdjustDown(i);
    			}
    		}
    		//弹出顶部数据
    		void pop()
    		{
        
    			swap(_con[0], _con[_con.size() - 1]);
    			_con.pop_back();
    			AdjustDown(0);
    		}
    		//插入数据
    		void push(const T&x)
    		{
        
    			_con.push_back(x);
    			AdjustUp(_con.size() - 1);
    		}
    		//访问顶部数据
    		const T& top()
    		{
        
    			return _con[0];
    		}
    		//数组大小
    		size_t size()
    		{
        
    			return _con.size();
    		}
    		//是否为空
    		bool empty()
    		{
        
    			return _con.empty();
    		}
    
    	private:
    		Container _con;
    	};
    
    }

*测试*

#include<iostream>
    using namespace std;
    
    #include"priority_queue.h"
    
    
    int main()
    {
        
    	int a[9] = {
         4,8,1,9,6,7,2,5,5};
    	mine::priority_queue<int> v(a,a+9);//使用区间初始化
    
    
    	mine::priority_queue<int> vv;//无参初始化
    	vv.push(5);
    	vv.push(2);
    	vv.push(7);
    	vv.push(11);
    	while (!vv.empty())
    	{
        
    		cout << vv.top() << ' ';
    		vv.pop();
    	}
    	return 0;
    }

## 三.仿函数 ##

### 1.优先队列里的使用 ###

> **在库里除了T,Container两个模板参数外，还有一个Compare参数，这是一个仿函数用来改变存储顺序(默认是less，也就是大堆，可以改成greater，也就是小堆)**

![在这里插入图片描述][247667c787e9431e8c295488c0d3de27.png]

![在这里插入图片描述][a0094f989e844fb29051871f586adf5f.png]

![在这里插入图片描述][f99f8dffe559467083c43c09f32a2241.png]

![在这里插入图片描述][d82564fd51bd4fc0a06e35f1d53e7f41.png]

![在这里插入图片描述][8ebbf2fe69e84e8a9a515f18c4c4cc5c.png]

### 2.概念 ###

> **仿函数的底层实际很简单，就是一个类里面重载了一个括号（）运算符。**

![在这里插入图片描述][28092748b44145f78393e2945b2b1110.png]

![在这里插入图片描述][f2013b91bd3847e49e80350253c6fc40.png]

> **仿函数的本质就是一个类的对象可以像函数一样使用。**

### 3.模拟 ###

> **由于less,greater本质都是类，库里有实现，所以就可以直接使用。**

#include<vector>
    
    namespace mine
    {
        
    	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 (com(child + 1, _con.size()) && com( _con[child], _con[child + 1]))
    				{
        
    					child++;
    				}
    				if (com(_con[parent],_con[child]))
    				{
        
    					swap(_con[child], _con[parent]);
    					parent = child;
    					child = parent * 2 + 1;
    				}
    				else
    				{
        
    					break;
    				}	
    			}
    		}
    
    		//向上调整
    		void AdjustUp(int child)
    		{
        
    			Compare com;
    			int parent = (child - 1) / 2;
    			while (child > 0)
    			{
        
    				if (com(_con[parent],_con[child]))
    				{
        
    					swap(_con[child], _con[parent]);
    					child = parent;
    					parent = (child - 1) / 2;
    				}
    				else
    				{
        
    					break;
    				}
    			}
    		}
    	public:
    		//无参构造
    		priority_queue()
    		{
        }
    		//区间构造
    		template<class InputLterater>
    		priority_queue(InputLterater first,InputLterater last)
    		{
        
    			while (first != last)
    			{
        
    				_con.push_back(*first);
    				first++;
    			}
    
    			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
    			{
        
    				AdjustDown(i);
    			}
    		}
    		//弹出顶部数据
    		void pop()
    		{
        
    			swap(_con[0], _con[_con.size() - 1]);
    			_con.pop_back();
    			AdjustDown(0);
    		}
    		//插入数据
    		void push(const T&x)
    		{
        
    			_con.push_back(x);
    			AdjustUp(_con.size() - 1);
    		}
    		//访问顶部数据
    		const T& top()
    		{
        
    			return _con[0];
    		}
    		//数组大小
    		size_t size()
    		{
        
    			return _con.size();
    		}
    		//是否为空
    		bool empty()
    		{
        
    			return _con.empty();
    		}
    
    	private:
    		Container _con;
    	};
    
    }

[1510754bde4c4966aaa65ad509504a70.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/95bbdbcf4dcd4ec995f6e9ce981e6096.png
[3e393ab4b16644fe9206a3af7af1f154.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/6bb51cb6031444508cf2088b90fa7ac2.png
[c89e59b41fe24c67b3f7778f0563570c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/789dbd29f65649a4a93d3457cf9d2518.png
[cbf4fb48fc334fa582afd007f815cdf4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/477c8a78d2e04ad597dd3531d15023e7.png
[f0cc706d0a9049a6993daa562ca0722c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/2bcae4f1b21b462daed07dc08b7e8dcd.png
[247667c787e9431e8c295488c0d3de27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/33904375408f4c4f8a8bc01a3f0dd897.png
[a0094f989e844fb29051871f586adf5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e3ba1889a44d4aa2ad10dd5c0ff7a3b7.png
[f99f8dffe559467083c43c09f32a2241.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/0728156543464d9a83a3ab7cf59d47c5.png
[d82564fd51bd4fc0a06e35f1d53e7f41.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/1b3b9a0795ff4e07b0adfc1d9e3774cd.png
[8ebbf2fe69e84e8a9a515f18c4c4cc5c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/5a59461c77e449558cafb09d176f4d5b.png
[28092748b44145f78393e2945b2b1110.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/c656efdb57614903be9a5f02ae1168f0.png
[f2013b91bd3847e49e80350253c6fc40.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/83da48e1afee4f878efc64ae7246726a.png