数据结构 【堆实现】

        上文提到堆是一种特殊的二叉树，其中它的父结点均不大于或者不小于其子结点的值。堆总是一棵完全二叉树。其中，堆的父节点全部不小于它的子结点时称为大堆，堆的父结点全部不大于其子结点的堆称为小堆。

        堆可以由两种结构来实现，分别是顺序结构和链式结构。这里我们先来实现堆的顺序结构。

        堆中各结点的父节点与子节点在数组中存放的位置有下面的关系：

         下面，我们就来一起实现一下堆这个数据结构。

1、准备工作

        这里我们要实现的是顺序结构存储堆，所以底层为数组，也就是顺序表的形式。先定义顺序表的结构。

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

        定义好顺序表的结构之后就需要对创建堆并对其进行初始化了。

2、堆的初始化 

        这里使用接收结构体指针的方式来进行实现，先创建一个堆对象，传入这个对象的地址。使用malloc为数组开辟空间，并将size和capacity赋初值。

void HeapInit(HP* php)
{
	assert(php);

	HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	php->a = tmp;
	php->size = 0;
	php->capacity = 4;
}

3、堆的数据插入

        这里实际上就是在数组中插入一个数据，但是与前面的顺序表插入数据不同之处在于，堆在插入数据之后需要进行调整，我们这里以大堆为例。再插入数据之后假设插入的数据大于它的父结点，那么就需要和它的父结点交换位置。逻辑上是这样的：

        在这部分称之为向上调整。向上调整过程中，假设子结点的数据大于父结点的数据就进行交换位置。

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(HPDataType* a,int child)
{
	int parent = (child - 1) / 2;
	while (parent >= 0)//parent<0就停止
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;//进行迭代
		}
		else 
		{
			break;//a[child] < a[parent]跳出
		}
	}
}


void HeapPush(HP* php, HPDataType val)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity *= 2; 
	}

	php->a[php->size] = val;
	php->size++;
	AdjustUp(php->a,php->size-1);//向上调整

}

3、堆顶的删除

        在堆的删除这里，我们需要删除的是堆顶元素。我们知道，对于数组来说删除数组的第一个元素并不是很容易。这里我们使用一个新的思路：将堆顶元素与最后一个元素进行交换位置，再删除掉数组末尾位置的元素。

        上面的思路就可以写成下面的形式：

void AdjustDown(HPDataType* a, int parent,int size)
{
	int maxChild = 0;
	
	while (parent <= size)
	{
		int leftChild = parent * 2 + 1;
		int rightChild = parent * 2 + 2;
		maxChild = leftChild;//找到最大的子结点进行交换
		if (a[rightChild] > a[leftChild])
		{
			maxChild = rightChild;
		}

		if (maxChild <= size && a[parent] < a[maxChild])//防止越界访问
		{
			Swap(&a[parent], &a[maxChild]);
			parent = maxChild;
		}
		else
		{
			break;
		}
	}
}

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