【数据结构初阶】--- 堆

一、什么是堆？

堆其实就是个完全二叉树

树

先了解一下什么是树
就像链表中的节点，不过树中的节点至少指向一个或多个节点，但是，一个结点不能被多个节点指向

二叉树

堆是完全二叉树，那完全二叉树什么样呢？
先看看二叉树
像这样的，与普通的树不同在于二叉树中的每个结点只能指向两个不同的结点

完全二叉树

完全二叉树：

• 最后一行的节点从左到右是连续的，最少可以是一个结点
• 其余行必须是满的
• 当最后一行满结点时又叫做满二叉树，这是完全二叉树的特殊情况

接下来就要看看一下完全二叉树的样子

堆的分类

堆分为大堆和小堆

• 小堆：树任何一个父亲都小于等于孩子
  
• 大堆：树任何一个父亲都大于等于孩子
  

堆的实现方法

上面用图描述的堆实际上是逻辑模型，而真实的存放这些数据是用数组来存放，这也叫物理模型
90存在数组下标为0的位置，75存在数组下标为1的位置，80存在数组下标为2的位置，以此类推
好像明明可以用链表存储，为什么非要用数组呢?
因为根据堆的特点，是可以对无序的数组进行排序，并且时间复杂度是O（N*logN）级别的，这样的速度是很优秀的。

二、堆的操作

//堆的初始化
void HeapInit(Heap* hp);
//堆的销毁
void HeapDestory(Heap* hp);

//向堆中插入数据
void HeapPush(Heap* hp, HDataType x);
//删除堆顶元素
void HeapPop(Heap* hp);
//返回堆顶数据
HDataType HeapTop(Heap* hp);
//判断堆是否为空
bool HeapEmpty(Heap* hp);

//向上调整
void AdjustUp(int* arr, int n);
//向下调整
void AdjustDown(int* arr, int n, int pos);//n是数组的个数，pos是开始调整的位置

堆的定义

堆虽然是个完全二叉树，但它是为了服务数组实现高效排序，因此我们就用数组来实现堆

typedef int HDataType;
typedef struct Heap
{
	HDataType* arr;
	int size;//数组的有效存储个数
	int capacity;//数组的容量
}Heap;

1
2
3
4
5
6
7
8

初始化

给堆初始化时我并没有给其开辟空间，所以后面插入数据时才会开辟，那么capacity和size自然也是0，给指针arr置空

void HeapInit(Heap* hp)
{
	assert(hp);

	hp->arr = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
1
2
3
4
5
6
7
8

插入数据（包含向上调整详细讲解）

首先就是判断空间够不够，size如果等于capacity，那就表示已经满了，需要先扩容，这里是扩容，所以要用realloc，如果用malloc，那么之前的数据就丢失了，因为malloc的作用是重新开辟一块新的空间，而不是扩容，扩容是需要使原来的数据保存下来，并且有了新的空间区存放新的数据
接下来就是到了重要的时刻，向上调整AdjustUp，我用小堆来讲解
因为我们要在插入数据的同时要保证数组中的数据存储顺序与逻辑模型中的堆保持一致，新的数据是插在数组末尾的，现在整体看来已经不满足小堆了

• 每插入一个数据时，只与自己的父亲比较，如果自己比父亲小，那就与父亲交换值，交换后，再与当前位置的值进行比较，直至比父亲大的时候或者已经到根节点的时候，停止比较
• 为什么只与自己的父亲比较呢，因为当你插入时，此时的数据已经是个小堆了，那么你的到来只会影响你跟你父亲、你父亲的父亲…这些位置，所以每次跟这条线路的值比较就行
• 无论这个孩子是左孩子还是右孩子，想要找到父亲的位置，只需parent = (child-1)/2，就可以找到父亲的下标

void HeapPush(Heap* hp, HDataType x)
{
	assert(hp);

	if (hp->size == hp->capacity)
	{
		int new_capacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HDataType* p = (HDataType*)realloc(hp->arr, sizeof(HDataType) * new_capacity);
		if (p == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->arr = p;
		hp->capacity = new_capacity;
	}
	hp->arr[hp->size] = x;
	hp->size++;

	AdjustUp(hp->arr, hp->size);//当前个数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

向上调整

void AdjustUp(int* arr, int n)
{
	int child = n - 1;
	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

删除堆顶元素（包含向下调整详细讲解）

• 为什么是删除堆顶元素而不是删除堆的最后一个元素，毕竟插入的时候就是尾插
• 因为堆顶的元素是整个数组中最小的元素，我们可以利用这一特性来寻找数组中前多少位小的数，就像奶茶店寻找评分最高的十家店，现在是小堆，那我们就利用小堆寻找评分最低的十家店。
• 如果我们将现在的堆顶元素删除，那么现在没有了堆顶元素，谁来当堆顶元素呢，是像数组删除头元素，然后整体向前移一位吗？听起来好像有点意思，那就分析一下吧
  
• 左边是排好的小堆，右边是删除了20后，数组中每个数据向前移一位形成的“小堆”，此时，不难看出，这根本已经不是堆了，为什么？
• 因为堆的性质，父亲节点要小于等于两个孩子，与兄弟节点的大小没有任何关系，现在你变成了第二张图，30，原本是25的兄弟，他俩的大小本身是没有关系的，但是经过刚才的操作，30变成了25的父亲，在小堆中，作为父亲，就要比孩子小，原本我们是兄弟没有大小关系，我可以比你大，可以比你小，现在变成了父子，就有了大小关系，自然就有可能就不符合小堆的条件，
• 那么，还有没有挽回的余地呢，有的，将现在的数据重新排成小堆，但你要知道，删除一个堆顶元素，就要重新排一次全部数据，这样的代价是非常大的。有没有更好的方法，接下来我就会讲

向下调整：

• 想删除堆顶元素，那就与最后一个元素进行交换，然后size–，此时新的堆顶元素作为父亲与两个孩子中较小的一位比较大小，父亲比孩子大，那就交换，交换后的父亲继续与孩子比较，直至父亲比孩子小或者孩子的下标大于数组长度，到此停止，现在的数组存储数据的顺序，依旧是小堆。
• 为什么是和两个孩子中较小的比较呢？假设一下吧，首先作为父亲的两个孩子，他俩的大小是没有直接关系的，谁都可以比对方大或小，假设一个孩子大一个孩子小，父亲要跟孩子比，分三种情况，
  1. 父亲最大，与大孩子比较，父亲大，所以与大孩子交换，交换后，大孩子在父亲的位置，那就要比两个孩子都小，但大孩子本身就比小孩子大，所以还要和小孩子交换，经历了两次交换。
  2. 父亲比大孩子小，比小孩子大，那么父亲需要和小孩子交换，交换后，小孩子比之前的父亲和大孩子都小，所以只交换一次。
  3. 父亲是最小的，因此不需要交换，但是父亲即使没有交换，也是比较了大小才确认的。

总结：
当父亲之和小孩子比较大小时，要么交换一次要么不交换；与大孩子比较时，交换两次，交换一次，和不交换；相比之下，如果只与小孩子比较就会节省交换两次的操作，因此父亲与小孩比较大小就行。

void HeapPop(Heap* hp)
{
	assert(hp);

	Swap(&hp->arr[0], &hp->arr[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->arr, hp->size,0);//传的是当前的个数
}
1
2
3
4
5
6
7
8

向下调整

思路：

• 先将末尾的值与堆顶元素交换，此时想要保持整个数组还是小堆，就让现在的交换后堆顶元素向下调整
• 小堆的话，与两个孩子中较小的比较大小，如果比那个孩子小，那就交换，交换后重复这个过程，直至遇到较小的孩子都比自己大时或者自己的孩子的下标已经超出整个数组的大小，那就停止

void AdjustDown(int* arr, int n，int pos)
{
	int parent = pos;
	int child = parent * 2 + 1;

	while (child < n)
	{
		if (((child + 1) < n) && (arr[child] > arr[child + 1]))
		{
			child = child + 1;
		}
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

返回堆顶元素

HDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->arr[0];
}
1
2
3
4
5
6
7

判断堆是否为空

bool HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}
1
2
3
4
5
6

销毁

void HeapDestory(Heap* hp)
{
	assert(hp);

	free(hp->arr);
	hp->arr = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
1
2
3
4
5
6
7
8
9

三、建堆

意义：将乱序的数组调整成堆

向上调整建堆

虽然数组已经有了数据，但我们把建堆的过程看做插入数据，

向下调整建堆

• 不论是向上调整还是向下调整，都有前提，除当前位置，剩余的位置已经是堆了，比如向上调整，这个数到来之前就已经是个堆了，只不过由于它的到来，更改了堆的结构，所以向上调整为新的堆
• 那么向下调整也一样吗？首先想到的应该是从堆顶开始向下调整，关键是你是第一个元素，但其余的元素并不是堆，怎么办，要想向下调整，首先之前的结构要是堆。
• 方法不太好想，我就来讲解一下，堆是完全二叉树，它的叶子结点实际也就是一个个堆，比如图中的65、10、70、15都是堆，那么我们倒着向下调整来组建堆，这四个数已经是堆了，所以从80开始