【数据结构】再谈堆与优先级队列

堆是继栈、队列以及二叉树之后又一个重要的数据结构，堆在底层也是没有自己的容器的，而是通过binary heap这种complete binary tree（完全二叉树）来实现的。下面就堆的实现原理及底层容器作以阐述和实现。

1. 完全二叉堆

complete binary tree（完全二叉树），整棵树除了最底层的叶节点之外，是填满的，而最底层的叶节点由左至右不得有空隙，这样带来的好处是：我们可以利用array来储存所有的结点。

如上图所示，我们可以将完全二叉树的结点按照层序遍历的顺序储存在一个数组中，那么当完全二叉树中的某个结点位于array的i处时，其左子节点必位于2i+1处（i>=0），其右结点必位于array的2i+2处。这样我们就可以轻易的实现完全二叉树的存储。

若将结点v的编号（秩）记作i（v），则满足以下关系：

i(root) = 0;
i(leftChild(root)) = 1;
i(rightChild(root)) = 2;
i(leftChild(leftChild(root))) = 3;
....
 
对于任意结点，则有：
1)若v有左孩子，则 i(leftChild(v)) = 2 * i(v) + 1;
2)若v有右孩子，则 i(rightChild(v))= 2 * i(v) + 2;
3)若v有父节点，则 i(parent(v)) = i(v)/2 - 1;

一个array和一组heap算法（用于插入元素、删除元素、取极值，将某一个数组数据排列成一个heap），array的缺点是无法动态改变大小，而heap却需要这样的功能，因此，以vector代替array是再好不过了。

堆存储在下标为0开始计数的数组中，因此在堆中给定小标为i的结点时：

①如果i=0: 结点i是根节点，没有双亲节点；否则结点i的双亲结点为结点(i-1)/2。
②如果2*i+1>n-1: 则结点i无左孩子，否则结点i的左孩子为结点2*i+1。
③如果2*i+2>n-1: 则结点i无右孩子，否则结点i的右孩子为结点2*i+2。

2. 最大堆和最小堆

根据元素排列方式，heap可分为max-heap和min-heap两种，前者每个节点的键值（key）都大于或等于其子节点键值，后者的每个节点键值（key）都小于或等于其子节点键值。

因此，max-heap的最大值在根节点，并总是处于底层array或vector的头部。min-heap的最小值在根节点，总是位于底层array或vector的起头处。

//max-heap and min-heap
max-heap(最大堆):每个父节点的值都大于孩子节点。
min-heap(最小堆):每个父节点的值都小于孩子节点。

以测试用例数组的{3,4,6,5,7,2}为例，其大小堆结构分别为：

3. 源代码及注释

#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
#define DataType int
using namespace std;
template<class T>
class Greate//大堆
{
public:
	bool operator()(const T& left, const T& right)//仿函数，重载()大于
	{
		return left > right;
	}
};
template<class T>
class Less//小堆
{
public:
	bool operator()(const T& left, const T& right)//仿函数，重载()小于
	{
		return left < right;
	}
};
template<class T,class Compare = Greater<T>>//第二个模板参数默认为大堆
class Myheap
{
public:
	//空堆
	Myheap()
	{}
	Myheap(const T* arr, DataType size)
	{
		assert(arr);
		_heap.resize(size);//开辟空间(比vector的pushback好)
		for (size_t idx = 0; idx < size; ++idx)
		{
			_heap[idx] = arr[idx];
		}
		//size-1为最后一个节点的下标，(size-1-1)/2 = 父节点
		size_t Root = (size - 2) >> 1;
		for (DataType idx = Root; idx >= 0; idx--)
		{
			AdjustDown(idx);
		}
	}
	//判空
	bool Empty()const
	{
		return _heap.empty();
	}
	//堆的大小
	size_t Size()const
	{
		return _heap.size();
	}
	//堆顶元素
	T& Top()
	{
		assert(Size() > 0);
		return _heap[0];
	}
	const T& Top()const
	{
		assert(Size() > 0);
		return _heap[0];
	}
	void PushHeap(const T& elem)//向堆中插入元素
	{
		//先将新节点插入末尾
		_heap.push_back(elem);
		//在将最后一个元素向上调整
		AdjustUp(_heap.size() - 1);
	}
	void PopHeap()//从堆中取出堆顶的元素
	{
		assert(!Empty());//堆不为空
		//先交换堆顶节点与堆尾节点
		std::swap(_heap[0], _heap[_heap.size() - 1]);
		//删除最后一个节点
		_heap.pop_back();
		//从堆顶向下调整,存在多个节点时才调整
		if (_heap.size() > 1)
		{
			AdjustDown(0);
		}
	}
     //①先找最后一个非叶子结点
     //②如果当前结点的孩子结点左孩子大于右孩子，就让child指向最大孩子结点（右孩子存在）
     //③如果当前父结点小于孩子结点，交换，父节点指向孩子，孩子指向孙子
	void AdjustDown(DataType _root)//下滤
	{
		DataType Parent = _root;//此时传入的_root为倒数第一个非叶子结点
		DataType Child = Parent * 2 + 1;//左孩子的下标等于父节点*2+1
		Compare _Compare;//仿函数用于比较优先级
		//左孩子存在
		while (Child < _heap.size())
		{
			//右孩子存在且右孩子的值大于左孩子
			if (Child + 1 < _heap.size() && _Compare(_heap[Child+1],_heap[Child]))
			{
				Child = Child + 1;//让Child结点保存大值
			}
			//孩子结点的优先级大于父节点(Child的值大于Parent的值)
			if (_Compare(_heap[Child], _heap[Parent]))
			{
				std::swap(_heap[Child], _heap[Parent]);//交换两节点的值
				//下滤
				Parent = Child;//让父节点指向孩子节点
				Child = Parent * 2 + 1;//孩子节点指向孙子节点
			}
			//孩子结点的优先级小于父节点(Child的值小于Parent的值)，则不需要调整
			else
				break;
		}
	}
        //①传入尾节点
        //②只要当前节点未到根节点，就一直上滤
        //③孩子节点的优先级大于父节点的优先级，交换，孩子指向父亲，父亲指向爷爷
//注意：在此不用考虑左右子数谁大谁小，上调是如果孩子结点比父结点大，那它肯定比兄弟结点大。
	void AdjustUp(DataType Child)//上滤
	{
		//此时传入的Child为最后一个节点的坐标
		DataType Parent = (Child - 1) >> 1;
		Compare _Compare;//仿函数用于比较优先级
		//上滤的过程，只要没到根节点就一直上移
		while (Child > 0 )
		{
			//孩子节点的优先级大于父节点的优先级
			if (_Compare(_heap[Child], _heap[Parent]))
			{
				std::swap(_heap[Child], _heap[Parent]);//交换节点的值
				//上滤
				Child = Parent;//孩子节点指向父节点
				Parent = (Child - 1) >> 1;//父节点指向爷爷节点
			}
			//孩子节点的优先级小于父节点的优先级，不需要调整
			else
				break;
		}
	}
private:
	std::vector<T> _heap;
};

//test.cpp
#include "heap.h"
void Test()
{
	int Array[] = { 3 ,4 ,6 ,5 ,7 ,2 };
	Myheap<int,Greate<int>> _h(Array,sizeof(Array)/sizeof(Array[0]));
	cout << _h.Size() << endl;
	cout << _h.Top() << endl;
	_h.PushHeap(2);
	cout << _h.Size() << endl;
	cout << _h.Top() << endl;
	Myheap<int, Less<int>> _h1(Array, sizeof(Array) / sizeof(Array[0]));
	cout << _h1.Size() << endl;
	cout << _h1.Top() << endl;
	_h1.PushHeap(2);
	cout << _h1.Size() << endl;
	cout << _h1.Top() << endl;
	_h1.PopHeap();
	cout << _h1.Size() << endl;
	cout << _h1.Top() << endl;
	
}
int main()
{
	Test();
	system("pause");
	return 0;
}

4. 优先级队列

优先级队列的实现调用的是堆的方法。priority-queue带有权值观念，其内的元素并非依照被推入的次序排列，而是自动依照元素的权值进行排列。通过complete binary tree以vector为底层容器就可以实现底端加入元素，顶端取出元素的操作。

//优先级队列(调用堆的方法即可)
template<class T,class Compare = Greate<T>>
class PriorityQueue
{
public:
	PriorityQueue()
	{}
	void Push(const T& data)
	{
		_hp.PushHeap(data);
	}
	void Pop()
	{
		_hp.PopHeap();
	}
	bool Empty()const
	{
		return _hp.Empty();
	}
	const T& Top()const
	{
		return _hp.Top();
	}
	size_t Size()
	{
		return _hp.Size();
	}
protected:
	Myheap<T, Greate<T>> _hp;
};