数据结构——堆

目录

一、堆

1.1 堆的概念

1.2 堆的存储

1.3 堆的应用

二、堆的实现

2.1 堆的调整算法

（1）向下调整算法

（2）向上调整算法

2.2 堆的创建

2.3 堆的删除

三、堆的代码实现?

四、堆排序

4.1 原理

4.2 代码实现

---

一、堆

1.1 堆的概念

堆（Heap）是一种特殊的树，如果将一个集合中的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中，并满足一定的规则，则称为堆。堆的性质有：

• 堆中任意节点的值总是不大于或不小于其父节点的值
• 堆总是一颗完全二叉树

?【拓展补充】：满二叉树每一层都是满的；完全二叉树最后一层可以不满，但是从左到右必须是连续的

接下来引入大小堆的概念，这也是堆在建立之时必须遵循的规则，如果不满足其中任意一种便不能称为堆

大堆（大根堆/最大堆）：树中任何一个父节点都大于或等于子节点，根节点是最大值

小堆（小根堆/最小堆）：树种任何一个父节点都小于或等于子节点，根节点是最小值

1.2 堆的存储

因为堆是一种特殊的完全二叉树，其存储方式与完全二叉树的顺序存储方式相同。

顺序结构存储就是使用数组来存储，一般只有完全二叉树适合用数组来存储，因为非完全二叉树的元素不连续会造成空间的浪费

?使用数组来存储，父子节点的关系如下

父节点：（子节点-1）/ 2

左子节点：（父节点*2）+1

右子节点：（父节点*2）+2

1.3 堆的应用

1. 堆排序

2. TopK问题

3. 优先级队列

---

二、堆的实现

2.1 堆的调整算法

假设给出一个数组，我们在逻辑上可以将其看作一颗完全二叉树，但是这个数组不能被称为堆。通过使用堆的调整算法我们可以将其调整成一个大/小堆。

（1）向下调整算法

向下调整算法就是将目标节点与左右子节点对比，符合条件则交换

向下调整算法有一个前提：左右子树必须是堆

例如图中，以27为根的左右子树都满足小堆的性质，只有根节点不满足，所以只需要将其与左右子节点中较小的交换即可

（2）向上调整算法

向上调整算法就是将目标节点与父节点对比，符合条件则交换

堆的插入就需要用到向上调整算法，例如我们在一个小堆中插入了一个新的元素：

使用向上调整算法：

2.2 堆的创建

堆的创建是堆排序中的一个重要部分。如果要将一个数组构建成堆，使用向下调整算法是最优解。但是根节点的左右子树都不是堆，所以我们反其道而行之，从最后一个节点的父节点开始进行向下调整。

因为单个节点也能成堆，所以最后一层的所有叶子节点都可以被视为堆，接着我们就对数组进行从后向前遍历，从最后一个节点的父节点开始向下调整

例如这个数组，我们要将其构建成小堆，先将其看作一颗完全二叉树

然后从最后一个节点的父节点开始向下调整，因为要遵循小堆规则所以二者交换

交换完毕，遍历到前一个节点，此时父节点小于两个子节点，所以不需要交换，跳到10

此时父节点是10，左子节点是7，右子节点是3，3比7更小，所以将10与3交换

现在，小堆就建立完毕了

2.3 堆的删除

一般堆的删除是指删除堆顶的数据。但是我们不能直接将数组的元素向前挪动覆盖第一个元素，因为在逻辑结构上，不同节点之间的关系已经建立，如果单纯的进行元素挪动就会打破所有的关系，将整个堆破坏。

所以我们要先将堆顶的数据和最后一个数据交换，保持中间所有元素在堆中的相对位置不变，然后删除数组的最后一个元素，再进行向下调整。

---

三、堆的代码实现?

以小堆的创建为例，我们先创建一个头文件"Heap.h"和两个源文件"Heap.c"和"Test.c"

下面是"Heap.h"的代码：

#pragma once

#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}Heap;

void HeapInit(Heap* hp);//初始化堆

void HeapDestory(Heap* hp);//销毁堆

void AdjustUp(HPDataType* arr, int child);//向上调整（小堆）

void AdjustDown(HPDataType* arr, int size, int parent);//向下调整（小堆）

void HeapPush(Heap* hp, HPDataType x);//插入数据

void HeapPop(Heap* hp);//删除数据

HPDataType HeapTop(Heap* hp);//获取堆顶数据

int HeapSize(Heap* hp);//堆的有效数据个数

bool HeapEmpty(Heap* hp);//堆的判空

下面是"Heap.c"的代码：

void HeapInit(Heap* hp)//初始化堆
{
	assert(hp);
	hp->arr = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

void HeapDestory(Heap* hp)//销毁堆
{
	assert(hp);
	free(hp->arr);
	hp->arr = NULL;
	hp->size = hp->capacity = 0;
}

void AdjustUp(HPDataType* arr, int child)//向上调整（小堆）
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			HPDataType tmp = arr[parent];
			arr[parent] = arr[child];
			arr[child] = tmp;
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void AdjustDown(HPDataType* arr, int size, int parent)//向下调整（小堆）
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && arr[child + 1] < arr[child])
		{
			child = child + 1;
		}
		if (arr[child] < arr[parent])
		{
			HPDataType tmp = arr[child];
			arr[child] = arr[parent];
			arr[parent] = tmp;
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(Heap* hp, HPDataType x)//插入数据
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->arr, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->arr = tmp;
		hp->capacity = newcapacity;
	}
	hp->arr[hp->size] = x;
	hp->size++;
	AdjustUp(hp->arr, hp->size - 1);
}

void HeapPop(Heap* hp)//删除数据
{
	assert(hp);
	assert(!HeapEmpty(hp));
	HPDataType tmp = hp->arr[hp->size - 1];
	hp->arr[hp->size - 1] = hp->arr[0];
	hp->arr[0] = tmp;
	hp->size--;
	AdjustDown(hp->arr, hp->size, 0);
}

HPDataType HeapTop(Heap* hp)//获取堆顶数据
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->arr[0];
}

int HeapSize(Heap* hp)//堆的有效数据个数
{
	assert(hp);
	return hp->size;
}

bool HeapEmpty(Heap* hp)//堆的判空
{
	assert(hp);
	return hp->size == 0;
}

测试一下：

---

四、堆排序

4.1 原理

堆排序即利用堆的思想进行排序，分为两个步骤

1. 建堆
2. 利用堆的删除思想进行排序

例如我们要对一个数组进行降序排序，我们要先对目标数组进行建小堆，然后将根节点（数组第一个元素）与堆的有效范围内最后一个节点（数组有效范围内最后一个元素）交换，此时数组的最后一个元素就是最小值，将有效元素个数-1后进行向下调整。调整完后根节点就是整个数组的第二小值，再重复前面的操作。

如果要进行升序排序，就要先建大堆，在函数中修改符号即可

4.2 代码实现

下面是堆排序的代码

void Heapsort(int* a, int size)
{
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
    // size-1才是最后一个节点，所以(size-1-1)/2才是最后一个节点的父节点
	{
		AdjustDown(a, size, i);
	}
	while (size > 1)
	{
		int tmp = a[0];
		a[0] = a[size - 1];
		a[size - 1] = tmp;
		size--;
		AdjustDown(a, size, 0);
	}
}

测试一下

完.

PS：画图不易，觉得不错就点个赞吧(??? )