c++学习之优先级队列

目录

1.初识优先级队列   

库中的实现

使用优先级队列

2.优先级队列的实现

3.仿函数

利用仿函数实现的优先级队列

迭代器区间构造（建堆）

---

1.初识优先级队列   

    如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了优先级队列 这种数据结构。 优先级队列（priority queue） 是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有     

优先队列也是一种抽象数据类型。优先队列中的每个元素都有优先级，而优先级高（或者低）的将会先出队，而优先级相同的则按照其在优先队列中的顺序依次出队。

库中的实现

对于库中的实现，参数来说，可以看到也是给了容器模版（适配器），还给了缺省参数为vector。

其次有一个compare参数（默认下给了缺省参数less的一个对象），实际上还有一个对象greater，这决定了优先级是较大的优先（less），还是较小的优先(greater)。

注意这里与库中的sort的排序顺序是相反的。

       对于接口我们可以看到它与栈的结构很像，其次与堆的结构的结构也很像（我们在数据结构部分知道取堆顶元素），再结合优先级队列的概念，寻找元素的大小，仔细想想：那么实际上优先级队列是一个堆的结构，利用建大堆的方式获取最大的元素等。

实际上对于适配器，我们不仅仅只是数组，我们也可以传双端队列作为适配器也是可以的。

使用优先级队列

简单的使用下，我们可以看到这里在默认的情况下较大的数一个个输出，故默认情况下这里给的是大堆，取堆顶元素便是最大的（删除元素-我们调换堆顶的元素与末尾的元素，向下调整）。

因为是堆的结构，故我们可以知道优先级队列插入删除的时间线复杂度为logN,

void test() 
{
	priority_queue<int,vector<int> > p;//取大的  大堆
	//priority_queue<int,vector<int> ,greater<int> > p;//取小的  小堆
	//入队 
	p.push(1);
	p.push(2);
	p.push(3);
	p.push(4);
	p.push(5);
	p.push(6);
	//打印并出队 
	while(!p.empty())
	{
		cout<<p.top();
		p.pop();
	} 
 } 

通过给出参数的不同，我们可以改变优先级是大或是小。

2.优先级队列的实现

明白了优先级队列的结构之后，我们自己也可以简单实现一下优先级队列。

 这里我们先不知道compare是个啥，我们先实现出默认的大堆结构，也就是大的优先，然后就是给出类型模版和适配器。

//默认实现大的优先级队列 
namespace mypriority_queue
{
	template<class T,class Container = vector<T> >class priority_queue
	{
		public:
			//入优先级队列，本质上就是建大堆 
			void push(cosnt T& x)
			{
				//尾插
				_con.push_back(x); 
				//向上调整 
				adjust_up(_con.size()-1);//从尾插的位置想上调整 （尾插前size(),故减一） 
			
			}
			
			void adjust_up(int child)
			{
				size_t parent=(child-1)/2;
				while(child>0)
				{
					if(_con[child]>_con[parent]&&child>parent)
					{
						swap(_con[child],_con[parent]);	
						child=parent;
						paren=(parent-1)/2;
					}					
				}else
				{
					break;
				}		
			}
			//出优先级队列，删除堆顶元素(先交换，在尾删，在向下调整)
			void pop()
			{
				swap(_con[_con.size()-1],_con[0]);
				_con.pop_back();
				adjust_down(0);
			}	
			void adjust_down(int parent)
			{
				size_t child=parent*2+1;
				while(parent<_con.size())
				{
					if(child+1<_con.size()&&_con[chid+1]>a[parent])
					{
						++child;												
					}
					if(_con[chid]>a[parent])
					{
						swap(_con[child],_con[parent]);
						parent=child;
						child=child*2+1;
																
					}
					
				}else
				{
					break;
			    }
			}
			const T& top()
			{
				return _con[0];
			}
			bool empty()
			{
				return _con.empty();
			}
			size_t size()
			{
				return _con.size();
			}
		private:
			Container _con;
	}
 
 } 

其中拷贝构造等都不需要我们实现了，系统在调用时会调用我们的容器里的。

3.仿函数

上面已经实现了优先级队列以较大的为优先，那么较小的，我们也可以在实现一个，改变一下向上调整与向上调整的比较符号为小于，就是以小的为优先也就是小堆。

可是我们在用的时候没必要为两份差不多相同的代码搞两个的容器来让我们调用，需要大的用大的，要小的用小的，那么有没有办法可以通过参数的不同的就能直接改变函数成为大堆或小堆，即通过参数不同改变函数。

c++提供了仿函数来实现：

仿函数(functor)，就是使一个类的使用看上去像一个函数。其实本质就是类中实现一个重载(),operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

如下：

class Less
{
public:
	bool operator()(int x,int y)
	{
		return x>y;
	}
};
int main()
{
   	Less less;
   	cout<<less(2,3);
   	cout<<less.operator()(2,3);//两者本质一样 
   	return 0;
}

实际上本质上是一个类，类中实现了重载()，简写的时候，本质上是对象调用方法，但看起来像函数调用。

通过仿函数我们就可以实现利用对象调用函数，重载的越多，对象可以调用的也就多了，以这种方式优先级队列可以通过传对象的方法来实现，大的优先级和小的优先级都可以调用

利用仿函数实现的优先级队列

一般使用的时候我们都是将模版与重载（）结合起来。

改变传参的仿函数就是改变比较的符号，在通过对象调用：

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;
	}
};
namespace mypriority_queue
{
	template<class T,class Container = vector<T> ,class compare=Less<T> >class priority_queue
	{
		compare com;
		public:
			//入优先级队列，本质上就是建大堆 
			void push(const T& x)
			{
				//尾插
				_con.push_back(x); 
				//向上调整 
				adjust_up(_con.size()-1);//从尾插的位置想上调整 （尾插前size(),故减一） 
			
			}
			
			void adjust_up(int child)
			{
				int parent=(child-1)/2;
				while(child>0)
				{
					if(com(_con[child],_con[parent])&&child>parent)
					{
						swap(_con[child],_con[parent]);	
						child=parent;
						parent=(parent-1)/2;
					}					
				}else
				{
					break;
				}		
			}
			//出优先级队列，删除堆顶元素(先交换，在尾删，在向下调整)
			void pop()
			{
				swap(_con[_con.size()-1],_con[0]);
				_con.pop_back();
				adjust_down(0);
			}	
			void adjust_down(int parent)
			{
				size_t child=parent*2+1;
				while(parent<_con.size())
				{
					if(_con.size>child+1&&com(_con[child+1],a[parent]))
					{
						++child;												
					}
					if(com(_con[child],a[parent]))
					{
						swap(_con[child],_con[parent]);
						parent=child;
						child=child*2+1;
																
					}
					
				}else
				{
					break;
			    }
			}
			const T& top()
			{
				return _con[0];
			}
			bool empty()
			{
				return _con.empty();
			}
			size_t size()
			{
				return _con.size();
			}
		private:
			Container _con;
	}
 
 } 

对于c++提供的仿函数我们也可以用此替换函数指针，函数指针在实际的应用上比较麻烦，我们可以利用仿函数替换他。

那么现在我们就知道在库中就已经有实现的less和greater,我们可以直接调用库中的。

当然除了库中提供的的less与greater外，我们还可以实现自己所需要的类型的比较，比如对Data类型的数据作比较，我们可以实现自己的仿函数，在通过参数传递用来实现Data类比较。

其次算法库中也提供了许多对于堆的一些判断接口等：

可以看到有堆排序，建堆，出入堆等接口。

迭代器区间构造（建堆）

在原有基础上，添加了另一种初始化的方法，利用迭代器区间来直接完成建堆：

priority_queue()
		{
			
		 } 
		//迭代器区间初始化
		template <class Inputiterator>priority_queue(Inputoriterator first,Inputoriterator last)
		:_con(first,last)//容器提供有迭代器区间初始化 
		{
			//建堆：初始化之后--向下调整 
			for(int i=(_con.size()-2)/2;i>=0;i--)
			{
				//堆从最后一个parent开始调整 
				adjust_down(i);
			}
			 
			
		}

因为容器本身具有迭代器区间初始化，我们只需要再次调整即可，此外因为我们自己写入了带有参数的构造函数，那么就需要再补充一个本身的无参构造即可。