数据结构 -- 堆

一.堆的概念

1.1 堆是什么

? ? ? ? 堆也叫做优先队列，一些按照重要性或优先级来组织的对象称为优先队列。

1.2 为什么需要堆

? ? ? ? 在现实生活中，存在许多需要从一群人、一些任务或一些对象中找出“下一位最重要”目标的情况。例如：在平时处理事情的时候我们总会先把“下一个最重要的”的事情取出来先处理。在处理的过程中，可能还会有其他的事情加进来。因此在事情处理完的事情，我们又要重新找出“下一个最重要”的事情进行处理。

? 堆就是处理这种情况的，我们通常把堆中的数据按照一定的重要性进行排序，从而按照顺序一个个取出堆中的元素。

1.3 如何创建一个堆

? ? ? ? 通常来说，我们容易想到以下的方法：

? ? ? ? 对所有元素进行一次排序然后取出最大值。但这种方法不是很好。它多做了很多无用功。因为其实我可能只要取一个最大值就OK了，但是却画蛇添足地帮我把所有元素都排好序了。很浪费时间。排序的时间复杂度至少为O(nlogn),插入和删除操作的时间复杂度为O(n)。

? ?而理论上我们所要实现的优先队列的时间复杂度是可以比这个更优的。

二.堆的属性

2.1 定义

• 堆是一棵（近乎）满二叉树，我们可以用数组来实现这棵二叉树（因为如果是满二叉树的话，其极其符合数组的形式，并且节点也可以用下标来表示，下面会证明）。
• 堆中的数据是局部有序的。我们使节点储存的值和它的子节点之间存在某种关系,从而利用数组模拟出堆这种形式。

2.2 堆的类型?

1. 最大值堆：任意一个节点的值都大于它的子节点的值：这样根节点存储的就是这组数据的最大值。
2. 最小值堆：任意一个节点的值都小于它的子节点的值这样子根节点存储的就是这组数据的最小值。

?

?2.3 堆的特殊规律

? 既然堆的逻辑结构是完全二叉树，那么它就同样具有完全二叉树的性质?。

?? ?对于完全二叉树，若从上至下、从左至右编号，以根节点为0开始，则编号为i的节点，其左孩子节点编号为2i+1，右孩子节点编号为2i+2，父亲节点为 (i-1) / 2。?这个规律非常重要！！！

验证：

? ? 一棵节点个数为N的完全二叉树，其高度为 h = log 2 (N+1)，（2为底数）。?

三.堆的实现?

3.1 堆的基本结构

? 我们在上面讲解了，对于一个满二叉树形式的结构，我们可以用一个数组来模拟,但有时候我们也可以用其它类型来进行模拟，在库里面，其实底层是一个模板参数，堆可以根据传入的类型来更改底层类型，不过默认为vector.

如下：

namespace My {
	
	template<class T, class Container = vector<T>>
	class Priority_queue 
	{
	public:
	private:
	  Container _con;
	};

}

3.2 堆的向下调整算法?

? 向下调整：是让调整的结点与其孩子节点进行比较，若想将其调整为小堆，那么根结点的左右子树必须都为小堆，若想将其调整为大堆，那么根结点的左右子树必须都为大堆，一般用于创建堆。

（小根堆）示例：

??

向下调整算法的基本思想（最小堆示例）：

1. 从根结点处开始，选出左右孩子中? 值较小的孩子。
2. 让较小的孩子与其父亲进行比较。
3. 若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
4. 若小的孩子比父亲大，则不需处理了，调整完成，整个树已经是小堆了。

注意：这里我们的大根堆和小根堆的大小对比明显是完全不一样的，那么我们就需要写两个向下调整代码吗？ 不，不需要，我们可以在创建一个对象时传入一个仿函数，从而实现让用户自己来控制需要的堆。

? 模板修改 + 仿函数实现：

	//构建大根堆函数
	struct Less
	{
		bool operator()(int k1,int k2){
			return k1 < k2;
		}
	};

	//构建小根堆函数
	struct Greater
	{
		bool operator()(int k1, int k2) {
			return k1 > k2;
		}
	};

	//默认构建大根堆
	template<class T,class Kvalue=Less>

向下调整代码的实现：

//在类外，这个函数是完全不需要的，因此设置为private
private:

	void adjust_down(int parent) {
        //构建仿函数
		Compare _com;

		int child = parent * 2 + 1;
		while (child < _con.size()) {
            //判断右节点有没有越界，顺便求出两个节点较大值
			if (child + 1 < _con.size() && _com(_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;
			}
		}
	}

3.3 堆的创建

?我们都知道，堆的底层结构是一个数组类型， 那么我们除了让一个空堆一个个插入，还能直接用一个数组来构建堆吗，答案是完全可以。

?那么我们该如何做呢？ 首先，堆的底层结构就是一个数组类型，那么我们可以直接用堆内的数组 copy 一下 传入的数组，然后按照向下调整算法，构建一个堆。

? 从上面的向下调整算法我们得知，我们使用向下调整算法时，需要保证左右两个子树都为堆，因此，单纯的从头节点开始向下调整是不可以的。

? 这里，我们可以把最底层的节点看为一个个堆，从最底层开始调整，但是如果从最底层开始调节，又有点太浪费资源，这里建议：

? ?从最后一个父节点(size/2）-1?的位置逐个往前调整所有父节点（直到根节点）,确保每一个父节点都是一个最大堆，最后整体上形成一个最大堆 。

? ps：因为最后一个父节点，最多只有两个子节点，因此，它的左右子树也必定是一个堆。

	//在C++ 中 我们现在基本都用迭代器构造 因此，创建一个迭代器模板类型
    template <class InputIterator>
	Priority_queue(InputIterator first, InputIterator last)
		:_con(first, last)//直接调用底层数据结构的迭代器构造
	{   //这里减2 的原因是 数组下标的问题 因为从0开始，所以真正的大小应该减一，在带入先前的算法
		for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
			adjust_down(i);
		}
	}

3.4 堆的向上调整代码?

? ?向上调整：是让调整的结点与其父亲结点进行比较，当我们已经有一个堆，显然我们在头部插入数据，会破坏原有的堆结构，因此我们需要在堆的末尾插入数据，再对其进行调整，使其任然保持堆的结构，这里我们就需要用到堆的向上调整算法。

??

向上调整算法的基本思想：

1. 将目标结点与其父结点比较
2. 若目标结点的值比其父结点的值大，则交换目标结点与其父结点的位置
3. 将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大，则停止向上调整，此时该树已经是大堆了

代码示例：

void adjust_up(int child) {

	Compare _com;
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (_com(_con[parent], _con[child])) {
			swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

3.5 堆的插入

? ?我们直接对数组进行尾插，然后在插入位置向上调整，因为插入时，只改变插入位置到根这一条路径，因此，只向上调整一次即可。

? 代码示例：

	void push(const T& x) {

		_con.push_back(x);
		adjust_up(_con.size() - 1);
	}

3.6 堆的删除

??堆的删除这里我们有特殊的规则，像我们直接删掉尾部的数据，其实是不改变堆的结构的，但那样有意义吗？

? 堆本来就起到一个排序的作用，你怎么知道最后一位数据，到底是多少呢？堆只能取到头部的顺序，因此，在我们删除时，是删除头部的数据。

? 但是直接删除的话，会把我们的堆结构变得极其混乱，对此，我们提出了另一种解法：

? 我们把头元素和尾部元素进行一次交换，然后把新尾部删除，让新头部元素向下调整（这样交换后，头元素的左右依旧是堆结构，只需要一次调整就能得到一个新堆。

? 代码如下：

	void pop() {

		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		adjust_down(0);
	}

3.7 其它接口

	bool empty() const {
		return _con.empty();
	}

	size_t size() const {
		return _con.size();
	}

四.代码测试
??

oid test1() {
		My::Priority_queue < int> pq1;
		pq1.push(5);
		pq1.push(2);
		pq1.push(3);
		pq1.push(9);
		pq1.push(4);

		while (!pq1.empty()) {
			cout << pq1.top()<< endl;
			pq1.pop();
		}
	}

	void test2()
	{
		vector<int> v1 = { 1,3,4,5,8,10,12 };
		Priority_queue<int> q1(v1.begin(), v1.end());
		Priority_queue<int, vector<int>, Greater<int>> q2(v1.begin(), v1.end());


		cout << "size:" << q1.size() << endl;
		while (!q1.empty())
		{
			cout << q1.top() << ' ';
			q1.pop();
		}
		cout << endl;

		cout << "size:" << q2.size() << endl;
		while (!q2.empty())
		{
			cout << q2.top() << ' ';
			q2.pop();
		}
		cout << endl;
		


	}

答案：

?

五.完整代码?

My_Priority_Queue.h

#pragma once
#include<iostream>
#include<vector>

using namespace std;

namespace My {

	template<class T>
	struct Less {
		bool operator()(const T& t1, const T& t2) {
			return t1 < t2;
		}
	};

	template<class T>
	struct Greater {
		bool operator()(const T& t1, const T& t2) {
			return t1 > t2;
		}
	};

	template<class T, class Container = vector<T>, class Compare = Less<T >>
	class Priority_queue {

	public:
		Priority_queue() {
		}

		template <class InputIterator>
		Priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)
		{
			for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
				adjust_down(i);
			}
		}


		bool empty() const {
			return _con.empty();
		}

		size_t size() const {
			return _con.size();
		}

		void push(const T& x) {

			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}

		void pop() {

			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}

		const T& top() {

			return _con[0];
		}

	private:

		void adjust_down(int parent) {

			Compare _com;
			int child = parent * 2 + 1;
			while (child < _con.size()) {

				if (child + 1 < _con.size() && _com(_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 adjust_up(int child) {

			Compare _com;
			int parent = (child - 1) / 2;
			while (child > 0) {
				if (_com(_con[parent], _con[child])) {
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else {
					break;
				}
			}
		}

	private:
		Container _con;
	};


	void test1() {
		My::Priority_queue < int> pq1;
		pq1.push(5);
		pq1.push(2);
		pq1.push(3);
		pq1.push(9);
		pq1.push(4);

		while (!pq1.empty()) {
			cout << pq1.top()<< endl;
			pq1.pop();
		}
	}

	void test2()
	{
		vector<int> v1 = { 1,3,4,5,8,10,12 };
		Priority_queue<int> q1(v1.begin(), v1.end());
		Priority_queue<int, vector<int>, Greater<int>> q2(v1.begin(), v1.end());


		cout << "size:" << q1.size() << endl;
		while (!q1.empty())
		{
			cout << q1.top() << ' ';
			q1.pop();
		}
		cout << endl;

		cout << "size:" << q2.size() << endl;
		while (!q2.empty())
		{
			cout << q2.top() << ' ';
			q2.pop();
		}
		cout << endl;
		


	}
}

?test.cc

#include"My_Priority_Queue.h"


int main() {

	try
	{
		My::test2();
	}
	catch (...)
	{
		cout << "未知异常" << endl;
	}

	return 0;
}