（手撕）数据结构---＞堆

文章内容

一：堆的相关概念与结构

二：堆的代码实现与重要接口代码讲解

让我们一起来学习:一种特殊的数据结构吧！！！！

一：堆的相关概念与结构

在前面我们已经简单的学习过了二叉树的链式存储结构了，那么二叉树的顺序存储结构是啥呢？其实二叉树的顺序存储结构我们一般将他叫做堆。

二叉树为啥有两种形式的存储结构呢？因为堆是一种特殊的二叉树，它特殊的地方在于它的逻辑结构实际上是一颗完全二叉树，在物理结构上我们一般用数组来表示堆的结构,而如果不是完全二叉树我们一般不会用数组成为二叉树的结构，因为假如不是完全二叉树那么我们数组可能会浪费大量的空间。

用数组作为二叉树的结构的时候我们必须要知道的双亲结点与子节点的下标关系为：

leftchild=parent*2+1；

rightchild=parent*2+2；

parent=(child-1)/2;(child可以是左孩子也可以是右孩子)

如图：完全二叉树与非完全二叉树在使用顺序存储结构的区别：

在这里就能看出当结构不同时，我们需要采取不同的形式进行表示。

总结：堆在逻辑结构上是一棵完全二叉树，在物理结构上是一个数组。对于非完全二叉树我们不适用数组的结构表示二叉树。

堆的两种形式(判断数组是不是堆的方式)

大堆：树中所有的父亲结点都大于或等于孩子结点，且根节点的值是堆中最大的数据。

小堆：树中所有的父亲结点都小于或等于孩子结点，且根节点的值是堆中最小的数据。

这也引出了堆的特点：1：堆中某个结点的值总是不大于或不小于父亲结点的值。

2：堆总是一棵完全二叉树。

二：堆的代码实现与接口的讲解

由于堆所具有的特点我们定义堆的结构为一个数组，与我们的顺序表，栈的结构类似。

代码：


typedef int HeapDataType;

typedef struct Heap
{
	HeapDataType* a;
	int Size;
	int Capacity;
}HP;

接下来就是我们熟悉的接口了，一些不难理解的接口我就直接跳过，对其它类型的接口进行讲解。

初始化堆：其实这个接口有两种初始化的代码：1:就是不开辟空间，等我们实际插入数据的时候来考虑增容和开辟空间。2:是传入一个数组然后将这个数组里面的值拷贝到我们需要开辟的空间当中。

代码如下：

void InitHeap(HP* php)
{
	assert(php);
	php->a = NULL;
	php->Size = php->Capacity = 0;
}

堆的销毁：直接销毁我们动态开辟的空间。

代码如下：

void DestoryHeap(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->Capacity = php->Size = 0;
}

接下来我们先讲两个重要的关于堆的算法向上调整算法与向下调整算法

首先这两个算法的时间复杂度都是log(N)

这两个算法在建堆的时候作用很大

我们先讲解

向上调整算法

前提：我们所插入的值前面的结构必须是堆

接下来我们通过图的方式来讲解这个算法的工作原理

代码实现：

void AdjustUp(HeapDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//交换的过程
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

总结算法思想：以建大堆为列，将插入的值与双亲进行比较，如果插入的值大于它的双亲的值，那么就交换孩子与双亲，可能我们插入的值非常大，那么可能会到达根节点所以我们使用循环来进行完成，最坏的情况就是我们要向上调整高度次，而完全二叉树的高度我们之前也算过，所以时间复杂度为:log(N);

向下调整算法

使用前提：左右子树都是堆

简单图解向下调整算法：

代码如下：

void AdjustDown(HeapDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//找小的那个孩子
		if (child+1<n && a[child] >a[child + 1] )
		{
			child++;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

代码是按小堆而写的

注意：这里我们需要考虑到一种特殊的情况，就是当我们孩子结点为最后一个结点的时候那么我们对下标为child+1的结点访问时会越界，而且我们在判断左右孩子谁小的时候我们不需要假定左孩子小这样会有几种情况且很麻烦，所以我们先假定要左孩子小，每次在判断孩子与双亲结点谁小的前面，先拿左孩子右有孩子相互比较，然后我们取小的就行。

总结算法思想：将父亲结点与孩子结点中小的结点进行比较，然后按照时大堆还是小堆的逻辑进行相互的比较，当孩子结点为叶子结点的时候循环终止。

插入接口：要保证插入之后我们的堆还是原来的大小堆。

思想：我们先尾插一个值，然后将这个值进行向上调整，且每次在插入之前我们都需要进行扩容逻辑的判断。

代码如下：

void PushHeap(HP* php, HeapDataType x)
{
	assert(php);
	//先尾插到数组中去
	//先判断空间是否足够
	if (php->Capacity == php->Size)
	{
		int newcapacity = php->Capacity == 0 ? 4 : php->Capacity * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail:");
			exit(-1);
		 }
		php->a = tmp;
		php->Capacity = newcapacity;
	}

	php->a[php->Size] = x;
	AdjustUp(php->a, php->Size);
	
	php->Size++;
}

总结：扩容，插入，向上调整，这几个步骤就能将这个接口给实现。

堆的删除接口：这个接口需要借助向下调整算法来解决

接口作用，能够将二叉树中最大或最小的结点值给删除，让第二大或第二小结点的值展示出来。

算法思想：我们并不是通过移动空间来将二叉树中根节点的值给删除，因为顺序表的尾插的时间效率非常的大，所以我们一般时首先将根节点的值与最后一个值进行交换，然后再将交换后的结点进行向下调整，这样做可以得到第二大或小的值。

代码：

void PopHeap(HP* php)
{
	assert(php);
	//得有元素才能删除
	assert(php->Size > 0);
	//删除的步骤
	//1先将根结点与尾结点交换，在删除最后一个结点
	
	Swap(&php->a[0], &php->a[(php->Size) - 1]);
	--(php->Size);
	//2在进行向下调整
	AdjustDown(php->a, php->a[0],0);
}

总结：在删除之前我们还需要看我们的堆是否含有结点，然后在交换，向下调整，就可以完成这个接口了。

这个接口与判空接口和取堆顶接口，能让我们对我们的数据打印出来是升序的或者是降序的。

取堆顶元素的接口

思想：直接返回数组中元素下标为0的值就行

代码：

HeapDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->Size > 0);

	return php->a[0];
}

判断堆有多少个元素的接口

直接return size就行

int HeapSize(HP* php)
{
	assert(php);
	
	return php->Size;
}

堆的判空：只需要看size为不为0就行

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->Size == 0;
}

本章结束！！！欢迎大家的耐心观看