堆

堆的概述

堆作为一种树形结构，也是二叉树的一种应用。二叉搜索树是规定了节点之间的大小关系：左孩子<根节点<右孩子。而堆中规定的节点之间的次序是：根节点<左孩子，根节点<右孩子；根节点>左孩子，根节点>右孩子。前者我们称之为小顶堆，后者是大顶堆。不同的逻辑定义，会得到不同的性质。关于堆的一些性质描写叙述，我们在选择排序：堆排序中已具体介绍过。

堆的存储结构

堆是一种特殊的全然二叉树。通常所说的堆，就是指二叉堆。特殊是指它的节点大小次序是有规定的，但其本质还是一棵全然二叉树。而全然二叉树最经常使用的是顺序存储结构。例如以下图;

对于全然二叉树这样的特殊的情况，节点的层次序列就足以反映整个二叉树的结构。顺序方式是全然二叉树最简单、最节省空间的存储方式。以下给出最小堆的c++实现：

代码

类定义

#include<iostream>
#include<iomanip>
using namespace std;
//默认堆大小
#define DEFAULTSIZE 20
//堆空间每次的增量
#define INCREMENT 10
typedef int ElemType;
class MinHeap
{
private:
	//堆数组
	ElemType* array;
	//堆内存大小
	int heapsize;
	//堆中元素个数
	int elemsize;
	//向上调整
	void siftUp(int);
	//向下调整
	void siftDown(int);
public:
	//默认构造方法
	MinHeap();
	//拷贝构造方法
	MinHeap(MinHeap&);
	//指定数组构造堆
	MinHeap(ElemType*, int);
	//析构方法
	~MinHeap()
	{delete[]array;}
	//堆清空
	void clear()
	{elemsize = 0;}
	//堆空的推断
	bool empty()
	{return elemsize == 0;}
	//返回堆中元素个数
	int heapSize()
	{return elemsize;}
	//插入新的元素
	void insertHeap(ElemType);
	//删除元素
	bool deleteHeap(int);
	//获取堆顶元素
	ElemType top();
	//遍历堆
	void traverse();
	//堆排序
	void heapSort();
};

类实现

//默认构造方法
MinHeap::MinHeap()
{
	elemsize = 0;
	array = new ElemType[DEFAULTSIZE];
	if (!array)
	{
		cerr << "分配内存失败！" << endl;
		exit(0);
	}
}
//拷贝构造方法
MinHeap::MinHeap(MinHeap& heap)
{
	//若原堆中有元素，则清空
	if (array)
		delete[]array;
	array = new ElemType[heap.heapsize];
	if (!array)
	{
		cerr << "分配内存失败！" << endl;
		exit(0);
	}
	MinHeap(heap.array, heap.elemsize);
}
//指定数组构造堆
MinHeap::MinHeap(ElemType* a, int n)
{
	elemsize = n;
	heapsize = DEFAULTSIZE;
	while (heapsize < n)
		heapsize += INCREMENT;
	array = new ElemType[heapsize];
	if (!array)
	{
		cerr << "分配内存失败！" << endl;
		exit(0);
	}
	//赋值
	memcpy(array, a, n*sizeof(ElemType));
	//堆化数组
	for (int i = (elemsize - 2) / 2; i >= 0; i--)
		siftDown(i);
}
//插入新的元素
void MinHeap::insertHeap(ElemType data)
{
	/*
	新元素总是先加到最后，再调整堆
	所以插入操作总是能够成功的(相对于内存大小)
	*/
	//若堆内存已用完，则扩充堆内存
	if (elemsize >= heapsize)
	{
		heapsize += INCREMENT;
		array = (ElemType*)realloc(array, heapsize);
	}
	array[elemsize] = data;
	siftUp(elemsize);
	elemsize++;
}
//删除指定位置元素
bool MinHeap::deleteHeap(int pos)
{
	//堆空或位置不正确
	if (empty() || pos<0 || pos>=elemsize)
		return false;
	//删除时，总是用最后一个元素填充待删除的位置
	array[pos] = array[elemsize - 1];
	elemsize--;
	//从该位置向下调整堆
	siftDown(pos);
}
//获取堆顶元素
ElemType MinHeap::top()
{
	if (empty())
		return NULL;
	return array[0];
}
//向上调整
void MinHeap::siftUp(int pos)
{
	int i, j;
	//i为j的父亲
	j = pos, i = (pos - 1) / 2;
	while (i>=0)
	{
		if (array[j] >= array[i])
			break;
		swap(array[i], array[j]);
		j = i;
		i = (j-1) / 2;
	}
}
//向下调整
void MinHeap::siftDown(int pos)
{
	int i, j;
	i = pos, j = 2 * i + 1;
	while (j < elemsize)
	{
		if (j + 1 < elemsize && array[j + 1] < array[j])
			j++;
		if (array[i] <= array[j])
			break;
		swap(array[i], array[j]);
		i = j;
		j = 2 * i + 1;
	}
}
//遍历堆
void MinHeap::traverse()
{
	if (empty())
		return;
	for (int i = 0; i < elemsize; i++)
		cout << setw(4) << array[i];
	cout << endl;
}
//堆排序
void MinHeap::heapSort()
{
	if (empty())
		return;
	ElemType *a = new ElemType[elemsize];
	if (!a)
	{
		cerr << "分配内存失败！" << endl;
		exit(0);
	}
	memcpy(a, array, elemsize*sizeof(ElemType));
	int n = elemsize;
	while (n >= 1)
	{
		//把最小的元素调到最后
		swap(a[0], a[n - 1]);
		n--;
		//从堆顶向下调整
		int i, j;
		i = 0, j = 1;
		while (j < n)
		{
			if (j + 1 < n && a[j + 1] < a[j])
				j++;
			if (a[i] <= a[j])
				break;
			swap(a[i], a[j]);
			i = j;
			j = 2 * i + 1;
		}
	}
	//打印
	for (int i = elemsize - 1; i >= 0; i--)
		cout << setw(4) << a[i];
	cout << endl;
	//释放内存
	delete[]a;
}

主函数

//主函数
int main()
{
	cout << "******最小堆***by David***" << endl;
	//准备工作
	int elemsize;
	ElemType data;
	cout << "输入堆中元素个数 ";
	while (cin >> elemsize && elemsize <= 0)
		cout << "输入不正确！又一次输入 ";
	ElemType *array = new ElemType[elemsize];
	cout << "输入各元素 ";
	int i = 0;
	while (i < elemsize)
		cin >> array[i++];
	//建堆
	cout << "初始化堆" << endl;
	MinHeap heap1(array, elemsize);
	//測试各方法，在測试的过程中，不断遍历
	cout << "堆空 ";
	heap1.empty() ? cout << "Yes!" : cout << "No!";
	cout << endl;
	cout << "遍历堆" << endl;
	heap1.traverse();
	cout << "获取堆顶元素 " << heap1.top() << endl;
	cout << "堆排序" << endl;
	heap1.heapSort();
	cout << endl;
	int pos;
	cout << "删除下标为 ";
	cin >> pos;
	heap1.deleteHeap(pos) ? cout << "删除成功！" << endl : cout << "删除失败！" << endl;
	cout << "遍历堆" << endl;
	heap1.traverse();
	cout << endl;
	cout << "插入元素 " ;
	cin >> data;
	heap1.insertHeap(data);
	cout << "遍历堆" << endl;
	heap1.traverse();
	cout << endl;
	//測试拷贝构造函数
	cout << "创建新堆" << endl;
	MinHeap heap2;
	heap2 = heap1;
	cout << "堆空 ";
	heap2.empty() ? cout << "Yes!" : cout << "No!";
	cout << endl;
	cout << "遍历堆" << endl;
	heap2.traverse();
	cout << "清空堆" << endl;
	heap2.clear();
	cout << "堆空 ";
	heap2.empty() ? cout << "Yes!" << endl: cout << "No!" <<endl;
	delete[]array;
	cout << endl;
	system("pause");
	return 0;
}

执行  

同样的输入：

小结

堆的用处非常多，最经常使用的有实现堆排序、优先队列……。这里粘贴的是最小堆的代码，仅仅要稍作改变，就可以得到最大堆的实现代码。上面的最大堆执行结果，即是改动代码后的结果。

完整代码下载：最小堆、最大堆

转载请注明出处，本文地址：http://blog.csdn.net/zhangxiangdavaid/article/details/37518641

若有所帮助，顶一个哦！

专栏文件夹：

• 数据结构与算法文件夹 
• c指针