priority_queue的使用与模拟实现

admin管理员组

文章数量:1624327

目录

priority_queue的使用

priority_queue的介绍

priority_queue的定义方式

priority_queue成员函数的介绍

priority_queue的模拟实现

1：堆的向上调整算法

2：堆的向下调整算法

两种算法的比较与各自最佳使用 

priority_queue的模拟实现

---

priority_queue的使用

priority_queue的介绍

priority_queue是C++ STL中的一种容器适配器，它提供了一种优先级队列的实现。优先级队列是一种特殊的队列，具有自动排序的功能，使得队列中的元素始终按照一定的优先级顺序排列，通常是由比较函数或者元素自身的比较操作符来定义。

priority_queue中的元素按照优先级进行排序，最高优先级的元素永远位于队列的顶部，可以方便地获取到具有最高优先级的元素。

在priority_queue中，可以使用push操作添加元素，pop操作移除顶部元素，top操作获取顶部元素（即具有最高优先级的元素）等。

priority_queue的底层实现通常采用堆（heap）数据结构，一般情况下是最大堆（元素值大的在顶部）或最小堆（元素值小的在顶部）。（也就是说默认为大堆存贮）

总的来说，priority_queue提供了一种方便高效的优先级队列实现，对于需要按照优先级排列元素的情况下很有用。

priority_queue的定义方式

方式一： 使用vector作为底层容器，内部构造大堆结构。

priority_queue<int, vector<int>, less<int>> q1;

方式二： 使用vector作为底层容器，内部构造小堆结构。

priority_queue<int, vector<int>, greater<int>> q2;

方式三： 不指定底层容器和内部需要构造的堆结构。

priority_queue<int> q;

注意： 此时默认使用vector作为底层容器，内部默认构造大堆结构

priority_queue成员函数的介绍

成员函数	功能
push()	插入元素到队尾（并排序）
pop()	弹出队头元素（堆顶元素）
top()	访问队头元素（堆顶元素）
size()	获取队列中有效元素个数
empty()	判断队列是否为空
swap()	交换两个队列的内容

使用案列举例：

#include <iostream>
#include <queue>
#include<vector>
using namespace std;
int main()
{
	priority_queue<int> q;
	q.push(3);
	q.push(6);
	q.push(0);
	q.push(2);
	q.push(9);
	q.push(8);
	q.push(1);
	q.push(10);
	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl;
	return 0;
}



打印结果：
//10 9 8 6 3 2 1 0

priority_queue的模拟实现

 上面也介绍了，优先接队列的底层实现通常采用堆（heap）数据结构，在默认大堆的情景下，我们在这里温习一下堆的几个关键性操作。

1：堆的向上调整算法

假如我们已经建立了这样的一个大堆， 如果在push7，那么就会在5的右子树先插入7，变为如图所示；

然后根据向上调整，由大堆的优先级比较，会与5进行交换 

然后再次与6根据大堆的优先级比较后得知还需要与6进行交换 

同理得知，就不需要再次9进行交换调整堆了。这就是向上调整。 

2：堆的向下调整算法

就比如这样一个堆，我们要进行向下调整的算法，那么他就有一个前提，那么就是图中用蓝色框起来的左子树与右子树要保证是大堆。

 向下调整其中有一个要注意的细节点，就是假如堆的顶部是5，5<6也5<8，5既可以与8交换也可以与6交换，但是如果与6交换后此时的顶是6但是6<8，还需要进行交换，所以向下调整算法有一个注意点就是：向下调整要与他的两个子结点中最大的哪一个进行交换。

当然这种特殊情况，对于图中给出的案例是不涉及的，不需要进行考虑。

只需要将7与8进行交换就完整了整个调整的过程 

两种算法的比较与各自最佳使用 

对于一个已经是大堆的情况下：

设节点总数为 n，则树的高度为 log⁡n。由此可知，堆化操作的循环轮数最多为 log⁡n次 ,所以两种调整的算法，最差的时间复杂度就为0(logn);所以在此情况下，两种堆的调整算法以时间复杂度来说是大差不差的。

但是你肯定听过一句这样的话：向下调整的效率>>向上调整，那么这句话是从何而来呢？

这其实是涉及到给你一个已知的一个乱序数组，然后分别利用两种算法来进行调整，在这种情景下来说：向下调整的效率>>向上调整。

我也找到了对应的别人的推导算法：

本图找自：堆的向下调整算法、堆的向上调整算法、堆的基本功能实现_堆的调整-CSDN博客

向上调整的没有找到，那么就由我来补充推到：

因为=(N+1)[log(N+1)-2]

用大O的渐进表示法：
T ( n ) = NlogN>>N

所以这也就是为什么会有向下调整的效率远远大于向上调整。

两种调整的匹配使用情况：

向下调整可以运用到用数组初始化堆，向上调整可以运用到入堆，对于删除堆顶的操作，是先将堆顶与堆低进行交换后，删除堆底后，在对顶用进行向下调整；

 说到这里了，那么这里就给出两种调整的算法实现把：

void adjustment_prev(Hp* php,int child)//升的排序   大堆
{
	assert("php");
	assert(!HeapEmpty(php));
	int parent = (child - 1) / 2;
	while (parent>=0)
	{
		if (php->a[child] > php->a[parent])//调换
		{
			swap(&php->a[child], &php->a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			//不交换
			break;
		}
	}
}
void adjustment_down(HpDataType* a,int n,int parent )
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if ((child + 1 < n) && (a[child] > a[child + 1]))
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

priority_queue的模拟实现

成员函数	实现方法
push()	在容器尾部插入元素后进行一次向上调整算法
pop()	将容器头部和尾部元素交换，再将尾部元素删除，最后从根结点开始进行一次向下调整算法
top()	返回容器的第0个元素
size()	返回容器的当前大小
empty()	判断容器是否为空

template<class T, class Container = vector<T>, class Compare = Less<T>>
class priority
{
public:
	priority()
	{}
	template <class InputIterator>
	priority(InputIterator first, InputIterator last)
		:_con(first, last)
	{
		for (int i = (_con.size() - 2) / 2; i >= 0; --i)
		{
			adjust_down(i);
		}
	}
	void adjust_up(size_t child)
	{
		Compare com;
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			//if (_con[parent] < _con[child])
			if (com(_con[parent], _con[child]))
			{
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}
	void push(const T& x)
	{
		_con.push_back(x);
		adjust_up(_con.size() - 1);
	}
	void adjust_down(size_t parent)
	{
		Compare com;
		size_t child = parent * 2 + 1;
		while (child<_con.size())
		{
			//if (child + 1 < _con.size()
				//&& _con[child] < _con[child + 1])
			if (child + 1 < _con.size()
				&& _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);
	}		
	const T& top()
	{
		return _con[0];
	}
	bool empty()
	{
		return _con.empty();
	}
	size_t size()
	{
		return _con.size();
	}
private:
	Container _con;
};	

需要解释的一点就是整个库函数，其实跟qsort差不多，但是整个是对应的建立大堆时使用的函数，他的作用就是比较两个数 

就比如上图中的这个使用情况，如果操作数一<操作数二，那么就返回真。

本文标签： priorityqueue