堆的实现

前言：本文讲述堆实现的几个难点，注意本文主要是以实现为主，建议有些基本概念认识的人阅读。

1.堆

2.堆的实现

堆结构的定义：

要实现的接口：

接口的实现：

堆的初始化和销毁：

向堆中插入数据：

Pop出堆顶的数据

判空，堆的大小和获得堆顶的值

1.堆

堆的分类：

大堆：

任意父节点都大于等于子节点

小堆：

任意父节点都小于等于子节点

逻辑结构：是满二叉树或完全二叉树

物理结构：数组

一组重要结论通过下标来确定数组中个元素之间的父子关系：这个是重点

leftchild = 2 * parent+1;（左孩子的下标等于父节点下标乘2加1）

rightchild = 2* parent +2;（右孩子的下标等于父节点下标乘2加2）

parent = (child-1)/2;（父亲节点的下标等于任意孩子节点的下标减1除2）

2.堆的实现

这里实现的是小堆

堆结构的定义：

typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* a;
	int size;
	int capacity;
}Heap;

因为物理结构是数组，所以要考虑扩容的问题。

要实现的接口：

//初始化
void HeapInit(Heap* php);
//销毁
void HeapDestroy(Heap* php);
//插入数据
void HeapPush(Heap* php,HeapDataType x);
//将堆顶的数据pop出
void HeapPop(Heap* php);
//判断堆是否为空
bool HeapEmpty(Heap* php);
//堆中元素的个数
int HeapSize(Heap* php);
//返回堆顶的数据
HeapDataType HeapTop(Heap* php);

接口的实现：

堆的初始化和销毁：

void HeapInit(Heap* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->a);
	php->size = 0;
	php->capacity = 0;
}

向堆中插入数据：

//交换数据
void Swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向上调整算法
void AdjustUp(HeapDataType* a, int child)
{
	int parent = (child - 1) >> 1;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) >> 1;
		}
		else
		{
			break;
		}
	}
}
//向堆中插入数据
void HeapPush(Heap* php,HeapDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HeapDataType* tmp = (HeapDataType*)realloc(php->a,sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size++] = x;
	AdjustUp(php->a, php->size - 1);
}

向堆中插入数据的步骤：

1.先考虑是否扩容

2.将需要插入的数据先插入数组下标为size的位置，之后在++

3.插入后需要根据自己的需求来实现向上调整算法

这里的难点是如何实现向上调整算法

通过父节点与子节点的大小比较（正是这个比较的条件决定了建的是大堆还是小堆）来确定父节点与子节点的数据是否发生调换。本文实现的是小堆。你将文章中子节点与父节点的大小比较的比较符号调换一下位置就变成了大堆

还有一点就是向上调整算法的参数为什么要是数组元素的首地址，原因是为了实现后面的堆排序。

Pop出堆顶的数据

注意pop出的数据是数组下标为0的数据，而不是数组最后面的数据

这里建的是小堆

//向下调整算法
void AdjustDown(HeapDataType* a, int size, int parent)
{
	int child = 2 * parent + 1;
    //最坏，左孩子>=size时循环结束，此时的parent是叶节点
	while (child<size)
	{
        //下面的两个条件不能调换位置，不能调换的原因是防止child+1>=size造成非法访问       
		if (child+1<size&&a[child + 1] < a[child])
			child++;
		if (a[child]<a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	int end = php->size - 1;
	Swap(&php->a[0], &php->a[end]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

步骤：

1.现将堆顶的数据和最后的数据交换，然后再将size--；

2.最后对刚换上去的堆顶的数据，采用向下调整算法。

为什么pop出堆顶的数据，不直接将数组的数据整体前移一个单位？

答：如果这样做的话，那么堆之间的关系就乱了，需要重新建堆，效率低

那么接下来的难点就是如何实现向下调整算法

代码解释：

图解：

判空，堆的大小和获得堆顶的值

bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}
int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}
HeapDataType HeapTop(Heap* php)
{
	assert(php);
	return php->a[0];
}

这里比较简单就不多讲了。

结语：下一篇的博客将讲讲堆排序的详细内容