STL源码剖析 | priority_queue优先队列底层模拟实现

 

 今天博主继续带来STL源码剖析专栏的第四篇博客了！
今天带来优先队列priority_queue的模拟实现！
话不多说，直接进入我们今天的内容！

---

前言

那么这里博主先安利一下一些干货满满的专栏啦！

手撕数据结构https://blog.csdn.net/yu_cblog/category_11490888.html?spm=1001.2014.3001.5482这里包含了博主很多的数据结构学习上的总结，每一篇都是超级用心编写的，有兴趣的伙伴们都支持一下吧！
算法专栏https://blog.csdn.net/yu_cblog/category_11464817.html这里是STL源码剖析专栏，这个专栏将会持续更新STL各种容器的模拟实现。

STL源码剖析https://blog.csdn.net/yu_cblog/category_11983210.html?spm=1001.2014.3001.5482

---

优先队列是什么

优先队列的底层实现就是数据结构的堆。其中，小顶堆可以不断更新数组里的最小值，大顶堆可以不断更新数组里的最大值，push和pop自带排序功能，经常用来解决TopK问题。

如果大家有需要数据结构堆的实现可以通过博主的传送门食用噢~

【堆】数据结构-堆的实现【超详细的数据结构教学】https://blog.csdn.net/Yu_Cblog/article/details/124944614

priority_queue的模拟实现

priority_queue底层是默认适配vector的，并且默认是大顶堆。

MyPriorityQueue.h

namespace yufc {
	template<class T, class Container = vector, class Compare = std::less>
													//默认是less  Compare是一个进行比较的仿函数
													//less -- 小堆
	class priority_queue {
	public:
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last) {
			while (first != last) {
				//不要直接去push，push调用的是向上调整，会慢很多
				//先弄进数组再建堆快一点，用向下调整
				_con.push_back(*first);
				++first;
			}
			//建堆
			for (int i = ((_con.size() - 1 - 1) / 2); i >= 0; i--) {
				adjust_down(i);
			}
		}
		//如果写了这个构造编译器就不会生成其它类型构造了，所以要自己写
		priority_queue() {}
		void adjust_up(size_t child) {
			Compare cmp;
			size_t parent = (child - 1) / 2;//找到父亲节点的下标
			while (child > 0) { //logn
				//if (_con[child] > _con[parent]) {
				//if (_con[parent] < _con[child]) {
				if (cmp(_con[parent],_con[child])) {
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else break;
			}
		}
		void adjust_down(size_t parent) {
			Compare cmp;
			size_t child = parent * 2 + 1;
			while (child < _con.size()) {
				//选出左右孩子中大的那个
				if (child + 1 < _con.size() && cmp(_con[child], _con[child + 1])) {
					++child;
				}
				if (cmp(_con[parent], _con[child])) {
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else break;//已经调整结束了，不用再调整了
			}
		}
		void push(const T& x) {
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}
		void pop() {
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		const T& top() {
			//返回值不允许修改 -- 修改了就不是堆了
			return _con[0];
		}
		bool empty() const {
			return _con.empty();
		}
		size_t size() const {
			return _con.size();
		}
	private:
		Container _con;
	};
}

测试代码

void test_priority_queue() {
	yufc::priority_queue<int,vector<int>,less<int>>pq; //底层是个堆
	//默认是大顶堆 -- 大的优先级高
	pq.push(3);
	pq.push(1);
	pq.push(2);
	pq.push(5);
	pq.push(0);
	pq.push(1);
	while (!pq.empty()) {
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
	int a[] = { 1,3,5,7,9,2,4,6,8,0 };
	yufc::priority_queue<int>pq1(a, a + sizeof(a) / sizeof(int));
	while (!pq1.empty()) {
		cout << pq1.top() << " ";
		pq1.pop();
	}
	cout << endl;
	//priority_queue<int>heap(a, a + sizeof(a) / sizeof(int));//这样构造也可以
	//如果想控制是小的优先级高呢？
	//我们要调整第三个模板参数，如果想传第三个，就必须传第二个
	priority_queue<int,vector<int>,greater<int>>heap(a, a + sizeof(a) / sizeof(int));//这样构造也可以
	while (!heap.empty()) {
		cout << heap.top() << " ";
		heap.pop();
	}
	cout << endl;
}

尾声

看到这里，相信大家对priority_queue的模拟实现已经有一定的了解了！这些容器的模拟实现，是我们掌握STL的开始，后面，博主将会给大家带来map、set、哈希等等STL容器的模拟实现，持续关注，订阅专栏，点赞收藏都是我创作的最大动力。

（转载时请注明作者和出处。未经许可，请勿用于商业用途 )
更多文章请访问我的主页

@背包https://blog.csdn.net/Yu_Cblog?type=blog