[数据结构与算法]模拟实现C++中priority_queue

priority_queue的介绍

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成
堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：
默认情况下priority_queue是大堆。

构造函数的基础使用

#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{
	// 默认情况下，创建的是大堆，其底层按照小于号比较
	vector<int> v{3,2,7,6,0,4,1,9,8,5};
	priority_queue<int> q1;
	for (auto& e : v){
			q1.push(e);
	}	
	cout << q1.top() << endl; 
	cout << q1.top() << endl;
	// 如果要创建小堆，将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
	cout << q2.top() << endl;
}

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

priority_queue的模拟实现

#pragma once
#include<vector>
#include<assert.h>
//使用优先级队列得注意：如果存放的是自定义类型得数据，这个类型得自己重载自己得> 和 < 的函数
namespace xjh{
	template<class T> //仿函数,它是一个类型，可以传给函数模板做参数
	struct Less{
		bool operator()(const T& x, const T& y)const{
			return x < y;
		}
	};
	template<class T> //仿函数,它是一个类型，可以传给函数模板做参数
	struct Greater{
		bool operator()(const T& x, const T& y)const {
			return x > y;
		}
	};
	template<class T,class Container = std::vector<T>,class Compare = Less<T>>
	class priority_queue
	{
	public:
		priority_queue(){}
		template<class InPutIterator>
		priority_queue(InPutIterator first, InPutIterator last)
			:_Con(first,last) //显示调用_Con的默认构造函数
		{
			//建堆
			for (int i = (_Con.size() - 1 - 1) / 2; i >= 0; i--){
				adJustDown(i);
			}
		}
	private:
		//调整前提，堆还是堆，其实用来对插入堆最后一个元素进行调整，搞出来的向上调整算法
		void adJustUp(size_t child){
			size_t parent = (child-1)/2;
			Compare com; 
			while (child > 0){
				//if (_Con[child] > _Con[parent]){
				if (com(_Con[parent], _Con[ child])){
					std::swap(_Con[child], _Con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else{
					break;
				}
			}
		}
		//向下调整算法，为的是用来建堆使用的
		void adJustDown(size_t parent){
			size_t child = 2 * parent + 1;
			Compare com;
			while (child <_Con.size()){
				//if (child+1<_Con.size() && _Con[child + 1] > _Con[child]){
				if (child + 1<_Con.size() && com(_Con[child], _Con[child+1])){
					child++;
				}
				//if (_Con[child] > _Con[parent]){
				if (com(_Con[parent], _Con[ child])){
					std::swap(_Con[child], _Con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				else{
					break;
				}
			}
		}		
	public:
		void push(const T& x){
			_Con.push_back(x);
			adJustUp(_Con.size() - 1);
		}
		void pop(){
			//assert(!_Con.empty());
			//交换堆顶和堆尾
			std::swap(_Con[0], _Con[_Con.size() - 1]);
			//删除堆尾相当于删除堆顶
			_Con.pop_back();
			//再对堆顶进行向下调整
			adJustDown(0);
		}
		const T& top() const{
			return _Con[0];
		}
		size_t size()const{
			return _Con.size();
		}
		bool empty() const {
			return _Con.empty();
		}
	private:
		Container _Con;
	};
}

测试接口代码

#include<iostream>
#include<vector>
#include"priority_queue.h"
using namespace xjh;

int main(){

	priority_queue<int,std::vector<int>,Greater<int>> q;
	q.push(1);
	q.push(12);
	q.push(9);
	q.push(19);
	q.push(3);

	while (!q.empty()){
		std::cout << q.top() << " ";
		q.pop();
	}
	return 0;
}