数据结构之堆（Heap）的实现

  堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构，所以堆也叫做二叉堆。

• 二叉堆满足二个特性：

  1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

  2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

  当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于   任何一个子节点的键值时为最小堆。

  最大堆和最小堆是堆数据结构的重点。堆排序中使用特别的多。

•  堆的存储一般是用一个数组实现的，当然也可以用链式存储，但是特别麻烦。

  如下我们给出一个数组：

  int* Arry={10,16,18,12,11,13,15,17,14,19};

  现在我们要根据这个数组来建一个不是真正意义上的堆。

 现在的堆并不是真正的堆，它不满足最大堆或者最小堆，所以它是无意义的，我们要调整这个“堆”让它变成最大堆或者最小堆，这一步操作就是调整堆。

 调整堆：首先我们要明确调整堆的目的就是让整棵树中的双亲节点都大于孩子节点（这里以最大堆为例），所以我们要从叶子结点开始调整，直到调整到根节点结束，可能调整好这棵树后，子树又不符合最大堆规则，转而调整子树，所以我们把这种方式叫下调（AdjustDown）

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;

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


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

template<class T,template<class> class Continer = Greater>//默认为大堆
class Heap
{
public:
	Heap(){};
	Heap(const T* a, size_t size, Continer<T> con);
	Heap(const vector<T>& v);
	void Push(const T& x);
	void Pop();
	T& GetTop();
	bool Empty();
	size_t Size();
	void HeapSort(T* a, size_t size);
protected:
	void _AdjustDown(size_t parent);
	void _AdjustUp(size_t child);
protected:
	vector<T> _a;
	Continer<T> _con;
};

template<class T, template<class> class Continer = Less>
Heap<T,Continer>::Heap(const T* a,size_t size ,Continer<T> con)
{
	_a.reserve(size);

	for (size_t i = 0; i < size; ++i)
	{
		_a.push_back(a[i]);
	}

	//建堆
	for (int i = (_a.size() - 2) / 2; i >= 0; i--)
		//从第一个非叶子结点开始下调，叶子结点可以看作是一个大堆或小堆
	{

		_AdjustDown(i);
	}
}
template<class T, template<class> class Continer = Less>
void Heap<T,Continer>::_AdjustDown(size_t parent)
{
	size_t child = parent * 2 + 1;
	size_t size = _a.size();
	while (child < size)
	{
		if (child + 1 < size&&_con(_a[child+1],_a[child]))
			//注意这必须是child+1更大或更小，所以把child+1放在前面
			++child;
		if (_con(_a[child],_a[parent]))
		{
			swap(_a[parent], _a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

  在这里是使用的类去封装堆结构，并且用了仿函数的方式去复用最大堆和最小堆的代码。在这里默认把堆调整为最大堆。

 以下是堆的调用：

	int array[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
	size_t size = sizeof(array) / sizeof(int);
	Greater<int> ger;
	Heap<int,Greater> h(array, size, ger);//因为默认为大顶堆，所以可以省略Greater

  我们的调整堆的操作是从二叉树的第一个非叶子结点开始调整。有的读者会问为什么不从最后一个结点调整呢？因为所有叶子结点我们都可以看作一个最大堆或者最小堆，我们完全不需要去调整。

 要调整为一个最小堆的话只要修改一下调用即可：

	int array[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
	size_t size = sizeof(array) / sizeof(int);
	Less<int> les;
	Heap<int，Less> h2(array, size, les);

• 向一个最大堆（最小堆中插入一个数据），让堆仍为最大堆（最小堆）。

   Push操作：向堆中插入一个数据，也就是往数组中插入一个数据，插入数据以后一般都不是最大堆（最小堆），我们得去调整。

 上调（AdjustUP）：把新插入的结点大于（小于）双亲节点则往上调，直到满足最大堆（最小堆）。

template<class T, template<class> class Continer = Less>
void Heap<T, Continer>::Push(const T& x)
{
	_a.push_back(x);
	_AdjustUp(_a.size() - 1);
}
template<class T, template<class> class Continer = Less>
void Heap<T, Continer>::_AdjustUp(size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (_con(_a[child] , _a[parent]))
		{
			swap(_a[child], _a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

•   删除最大堆（最小堆）中的根结点。

  我们把根节点删除以后剩下的结点就不构成一棵树结构了，所以我们可以换一种思路让堆保持原来的结构。

  方法就是把根节点和最后一个结点交换，删除最后一个结点，这样就不会破环结构了。

  把结点删除后，堆肯定不满足最大堆（最小堆）了，所以我们还要调整堆。这次我们要从根节点往叶子结点调，这样很快，因为原来的堆根节点的左右子树都已经满足大小堆了。利用下调来调整：

template<class T, template<class> class Continer = Less>
void Heap<T, Continer>::Pop()
{
	assert(!_a.empty());
	size_t size = _a.size();
	swap(_a[0], _a[size - 1]);
	_a.pop_back();
	_AdjustDown(0);
}

  堆和栈是计算机内存最常用的结构。

  有了最大堆和最小堆，我们可以利用他们的特性来实现堆排序。