数据结构之堆（Heap）的实现-创新互联

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

• 二叉堆满足二个特性：

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

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

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

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

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

 如下我们给出一个数组：

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

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

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

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

#pragma once
#include
#include
#include
using namespace std;

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


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

template class Continer = Greater>//默认为大堆
class Heap
{
public:
	Heap(){};
	Heap(const T* a, size_t size, Continer con);
	Heap(const vector& 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 _a;
	Continer _con;
};

template class Continer = Less>
Heap::Heap(const T* a,size_t size ,Continer 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 Continer = Less>
void Heap::_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 ger;
	Heap 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 les;
	Heap h2(array, size, les);

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

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

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

template class Continer = Less>
void Heap::Push(const T& x)
{
	_a.push_back(x);
	_AdjustUp(_a.size() - 1);
}
template class Continer = Less>
void Heap::_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 Continer = Less>
void Heap::Pop()
{
	assert(!_a.empty());
	size_t size = _a.size();
	swap(_a[0], _a[size - 1]);
	_a.pop_back();
	_AdjustDown(0);
}

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

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

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。