【C++ STL】-- priority_queue底层原理、使用、模拟实现

目录

priority_queue的使用：

priority_queue的默认定义的模板：

priority_queue的定义并初始化：

priority_queue的模拟实现：

堆的排序算法：

堆的向上调整算法核心：

堆的向下调整算法核心：

priortiy_queue接口的模拟实现

---

priority_queue的使用：

priority_queue的默认定义的模板：

注意：

• 默认情况下priority_queue是大堆。
• 默认情况下priority_queue是以vector作为底层容器

（大多数情况下都是使用vector作为底层容器即可，我们需要变动的只是存储类型、构造堆结构的形式）

方式一：规定的存储类型，默认内部构造大堆结构

//int类型：
priority_queue<int> q1;
//double类型
priority_queue<double> q2;

方式二：默认内部构造小堆结构

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

priority_queue的定义并初始化：

template 
         priority_queue (InputIterator first, InputIterator last,
                         const Compare& comp = Compare(),
                         const Container& ctnr = Container());

vector<int> v{ 1,2,3,4,5,6,7,8,9,10 };
//使用大堆结构
priority_queue<int> q1(v.begin(), v.end());
//使用小堆结构
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());

#include
#include
#include
using namespace std;
int main() {
	priority_queue<int> q1;
	for (int i = 0; i < 10; i++)
	{
		q1.push(i);
	}
	//q1：9 8 5 6 7 1 4 0 3 2
 
	vector<int> v{ 10,20,30 };
	priority_queue<int> q2(v.begin(), v.end());
	//q2：30 20 10
 
	q2.swap(q1);
	cout << q1.size() << endl;//输出：3
	cout << q2.size() << endl;//输出：10
	//q1：30 20 10
	//q2：9 8 5 6 7 1 4 0 3 2
 
	while (!q1.empty()) {
		cout << q1.top() << " "; 
		q1.pop();
	}
	cout << endl;
	//输出：30 20 10
 
    return 0;
}

---

priority_queue的模拟实现：

注意，下标计算父子间的关系：

• leftchild = parent * 2 + 1
• rightchild = parent * 2 + 2
• parent = (child - 1) / 2 (因为只会保留整数部分)

堆的排序算法：

       此处以小根堆为例；(向上调整算法用于存入数据）。

堆的向上调整算法核心：

（父节点与子节点大小的比较，子对父）

• 如果比父亲小，则交换，然后继续向上比较并调整（最多调整到跟节点就结束了）。
• 如果比父亲大，则调整结束。

堆的向下调整算法核心：

（父节点与子节点大小的比较，父对子）

• 如果比父亲小，则交换，然后继续向下比较并调整。（最多调整到叶子节点就结束了）
• 如果比父亲大，则调整结束。

本人的堆的算法博客：

• 【C语言】-- 数据结构 -- 堆的实现（小堆）
• 【C语言】-- 数据结构 -- 利用堆排序【具体函数实现】

priortiy_queue接口的模拟实现

        只要知道了堆的向上排序调整算法和向下排序调整算法后，其实prirotiy_queue的模拟实现几乎已经可以说是完成了。

难度提升：

        priortiy_queue是可以通过容量适配器实现less与gtreater实现，内部堆排序的结构不同。既然需要less与greater，我们也模拟实现一下。

template, class Compare = less>

template<class T>
class less { bool operator()(T& e1, T& e2) { return e1 < e2; } };
template<class T>
class greater { bool operator()(T& e1, T& e2) { return e1 > e2; } };

#include
#include
#include
using namespace std;
namespace qcr{
 
	template<class T>
	class less { bool operator()(T& e1, T& e2) { return e1 < e2; } };
	template<class T>
	class greater { bool operator()(T& e1, T& e2) { return e1 > e2; } };
 
	template<class T, class Container = std::vector, class Compare = less>
	class priority_queue {
	public:
		priority_queue():_con() {}
		template<class InputIterator>
		priority_queue(InputIterator begin, InputIterator end) : _con(begin, end) {
			//数据的输入
			//while (begin != end) {
			//	_con.push_back(*begin);
			//	++begin;
			//}
 
			//数据的大小堆建立
			for (int i = (_con.size() - 1 - 1) >> 1; i >= 0; --i)
				Adjust_down(i);
		}
 
		void Pop() {
			assert(!empty());
 
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			Adjust_down(0);
		}
 
		bool empty()const {
			return _con.empty();
		}
 
		size_t size()const {
			return _con.size();
		}
 
		void push(T x) {
			_con.push_back(x);
			Adjust_up(_con.size() - 1);
		}
 
		const T& top()const
		{
			return _con.front();
		}
 
		//向下排序
		void Adjust_down(size_t parent) {
			size_t child = parent * 2 + 1;
			while (child < _con.size()) {
				if (child + 1 < _con.size() && Compare()(_con[child], _con[child + 1]))
					++child;
				if (Compare()(_con[parent], _con[child])) {
					//将父节点子节点进行调换
					std::swap(_con[parent], _con[child]);
					//更新父、子节点的位置
					parent = child;
					child = parent * 2 + 1;
				}
				else{
					//堆已经建立成功
					break;
				}
					
			}
		}
 
		//向上排序
		void Adjust_up(size_t child) {
			size_t parent = (child - 1) >> 1;
			while (child) {
				if (Compare()(_con[parent], _con[child])) {
					//将父节点子节点进行调换
					std::swap(_con[parent], _con[child]);
					//更新父、子节点的位置
					child = parent;
					parent = (child - 1) >> 1;
				}
				else {
					//堆已经建立成功
					break;
				}
			}
		}
		Container _con;
	};
}