priority_queue的底层解剖：

一、priority_queue的介绍：

priority_queue的定义：
优先级队列是默认用vector作为底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue
其次它的底层包含的常用接口就下面几种

函数声明	接口说明
priority_queue()/priority_queue(first,last	构建一个优先级队列
top()	返回优先级队列最大（最小元素），即是堆顶元素
push()	在优先级队列中插入元素
pop()	删除优先级队列中最大或最小元素，即是删除堆顶元素
empty()	判断优先级队列是否为空

priority_queue的使用：
根据接口函数的说明，我们能知道优先级队列能处理找最值元素等一些算法的应用。比如TOP k问题 。

二、priority_queue的接口函数实现：

1.堆的实现：

我们要完成在优先级队列中的插入删除操作，首先需要完成将vector的数组物理逻辑变为堆结构
并且堆结构实际就是二叉树的其中一种的特殊结构树——完全二叉树
二叉堆使用数组（或向量）存储，具有以下父子节点关系：

父节点索引：parent = (child - 1) / 2

左子节点：left_child = parent * 2 + 1

右子节点：right_child = parent * 2 + 2
那我们每插入一个数据就要把插入后的数组变为堆那我们首先需要用到向上建堆法
heapify_up——向上建堆法：
优先级队列默认是大堆也就是父亲结点比左右孩子结点大，根结点是最大的它的优先级最高，top()返回的数据就是根结点的

	void heapify_up(int child,Compare com)
	{
		int 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;
			}
		}
	}

代码剖析：比较父亲结点与孩子结点的大小，孩子数据大就与父亲交换位置，这里的Compare是一个仿函数，com(_con[parent], _con[child])这个比较跟_con[parent]<_con[child]这样比较的结果是不变的，后面我会讲仿函数是什么这里只要能看懂核心代码就行

heapify_up——向下建堆法：
这个是删除根结点的元素后，需要把这个堆重新变为大堆就需要向下调整

//向下建堆法
void heapifydown(int parent)
{ Compare com;
	int child = parent * 2 + 1;
	int size = _con.size();
	while (child < size)
	{
		//判断是否存在右子树
		/*if (child + 1 < size && _con[child]< _con[child + 1])*/
		if(child+1<size&& com(_con[child],_con[child+1]))
		{
			++child;
		}
		/*if (_con[parent]<_con[child])*/
		if(com(_con[parent],_con[child]))
		{
			swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;

		}
		else {
			break;
		}
	}
}

代码剖析： 先判断左右孩子哪个更大，更大的就与父亲结点交换，然后再比较下一个的父亲结点与左右孩子，以此类推。

2.插入函数push()：

	void push(const T& val)
	{
		_con.push_back(val);
		int size = _con.size();
		//向上建堆法
		heapify_up(size - 1);

代码剖析： 这里只需要注意的是插入的元素是在尾部所以向上建堆的数据传的是size-1

3.取堆顶函数top()：

T& top()
{
	return _con[0];
}

4.删除函数pop()

void pop()
{
	int size = _con.size();
	swap(_con[0], _con[size-1]);
	_con.pop_back();
		heapifydown(0);

代码剖析：这里的删除堆顶数据就是与最后一个元素交换数据，然后再尾删掉，因为底层容器是vector，它的删除中尾删效率是O(1),所以才与最后一个元素交换再删除，然后再向下重新建堆

5:判空函数empty()

bool empty()
{
	return _con.size() == 0;
}

三、构造函数

1.迭代器区间构造

priority_queue() = default;
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
	:_con(first,last)
{
	/*while (first != last)
	{
		_con.push_back(*first);
		++first;
	}*/
	int size = _con.size();
	for (int parent = (size - 1 - 1) / 2; parent >= 0; --parent)
	{
		heapifydown(parent);
	}
private:
	container _con;
}

代码剖析：这里注意，只要写了构造函数编译器就不会生成默认构造函数，但在这个优先级队列的构成中，我们本质还是用vector这个容器去封装它故我们使用vector的默认构造函数就行，priority_queue() = default;这段代码写了编译器它就会自己生成默认构造函数

四、仿函数

我目前接受的仿函数的知识就是，它其实是一个类，它里面有个成员函数operator()重载括号的函数，比如建堆里的com(_con[parent],_con[child]),就能像函数一样去调用函数 `

	template <class T>
	//仿函数的应用
	struct less {
		bool operator()(const T& x,const T& y )
		{
			return x < y;
		}
};
	template <class T>
	struct greater {
		bool operator()(const T& x, const T& y)
		{
			return x >y;
		}
	};

比如在priority_queue中在建堆的时候就需要用到仿函数，可以说是代码板块的一个专业性提升，priority_queue的仿函数有个缺陷，它默认是less这个仿函数，它大的优先级高，回顾建堆的代码就是，数据大的往上走
仿函数的优点就是能与其他类内内联，没有内存的消耗，因为一般仿函数没有成员变量,而且编译器的默认比较的结果不符合你的预期的话也可以通过仿函数来自己定义达到你的预期效果
c++搞出仿函数本质就是抛弃函数指针因为函数指针的学习成本比较大因为与指针相关，再者：

1. 仿函数可以编译器内联，效率更高

2. 仿函数可以存成员变量，做更复杂的比较，函数指针做不到

3. 模板推导仿函数更干净，不用写繁琐函数指针类型

五、完整代码

namespace TAO {
	template <class T>
	//仿函数的应用
	struct less {
		bool operator()(const T& x,const T& y )
		{
			return x < y;
		}
};
	template <class T>
	struct greater {
		bool operator()(const T& x, const T& y)
		{
			return x >y;
		}
	};






	template <class T, class container=std::vector<T>,class Compare=less<T>>
	class priority_queue {
	private:
		//向下建堆法
		void heapifydown(int parent,Compare com)
		{
			int child = parent * 2 + 1;
			int size = _con.size();
			while (child < size)
			{
				//判断是否存在右子树
				/*if (child + 1 < size && _con[child]< _con[child + 1])*/
				if(child+1<size&& com(_con[child],_con[child+1]))
				{
					++child;
				}
				/*if (_con[parent]<_con[child])*/
				if(com(_con[parent],_con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;

				}
				else {
					break;
				}
			}
		}
		//向上建堆法
		void heapify_up(int child,Compare com)
		{
			int 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;
				}
			}
		}
	public:
	
		void swap(T& x, T& y)
		{
			T temp = x;
			x = y;
			y = temp;
		}
		void push(const T& val)
		{
			_con.push_back(val);
			int size = _con.size();
			//向上建堆法
			heapify_up(size - 1, Compare());

		}
		T& top()
		{
			return _con[0];
		}
		void pop()
		{
			int size = _con.size();
			swap(_con[0], _con[size-1]);
			_con.pop_back();
				heapifydown(0,Compare());
		}
		bool empty()
		{
			return _con.size() == 0;
		}
		priority_queue() = default;
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first,last)
		{
			/*while (first != last)
			{
				_con.push_back(*first);
				++first;
			}*/
			int size = _con.size();
			for (int parent = (size - 1 - 1) / 2; parent >= 0; --parent)
			{
				heapifydown(parent, Compare());
			}

		}

	private:
		container _con;
	};