【数据结构】堆的概念、结构、模拟实现以及应用

🕗 发布于 2024-12-10 13:01 数据结构

本篇我们来介绍一下数据结构中的堆。

1.堆的概念及结构

1）堆是一颗完全二叉树。

2）堆又分为大堆和小堆，大堆就是树里面任何一个父节点都大于子节点，所以根节点是最大值；小堆就是树里面任何一个父节点都小于子节点，所以根节点也是最小值。

大堆和小堆只要求了父节点与子结点之间的关系，并没有要求兄弟节点之间的关系。 所以说，小堆不一定是降序，大堆不一定是升序。

2.父节点和子节点的对应关系

假设父节点在数组的下标为i：

左孩子在数组的下标：2*i + 1；右孩子在数组的下标：2*i + 2；

假设子节点在数组中的下标为j：

父节点在数组中的下标：(j - 1) / 2；

3.小堆的实现

3.1 准备工作

建立一个头文件Heap.h，两个源文件Heap.c和test.c，存放内容如下。

在Heap.h中实现堆的结构。因为堆的底层是数组，所以堆的底层实现和顺序表的一样。

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

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

3.2 初始化和销毁

在Heap.h中进行函数声明。

void HPInit(Heap* hp);//初始化
void HPDestroy(Heap* hp);//销毁

在Heap.c中进行函数实现。记得包含头文件 #include "Heap.h"

void HPInit(Heap* hp)
{
assert(hp);
hp->a = NULL;
hp->capacity = hp->size = 0;
}
void HPDestroy(Heap* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->capacity = hp->size = 0;
}

3.3 push 插入数据

实现之前我们先来分析一下。

假如我们现在实现一个小堆，在下面的小堆里插入一个10。

此时已经它既不是大堆也不是小堆，就不是一个堆，所以我们需要将这个10向上调整，让它变成小堆。如下是逻辑结构上的变化。

物理结构上这个10，应该是插入在数组的结尾。

我们按照前面说过的父子关系来通过子节点的下标找父节点。

找到父节点之后，与此时的子节点10对比一下，父节点比子节点10大，两个交换位置。

然后再用同样的方法继续找父节点。

找到父节点之后，与此时的子节点10对比一下，父节点比子节点10大，两个交换位置。

然后再用同样的方法继续找父节点。

找到父节点之后，与此时的子节点10对比一下，父节点比子节点10大，两个交换位置。

所以插入的数据要和它所有的“亲”祖先比，直到它大与等与自己的父亲，或者自己成了根节点，没有比它更小的数了，就结束。

3.3.1 交换

因为交换函数用的地方很多，包括push，所以我们封装一下交换的代码，以便后续使用。

在Heap.h中进行函数声明。

void Swap(HpDateType* p1, HpDateType* p2);//交换

在Heap.c中进行函数实现。

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

3.3.1 向上调整

我们将向上调整的代码同样封装成一个函数。

在Heap.h中进行函数声明。

void AdjustUp(HpDateType* x, int child);//向上调整

第一个参数是要调整的数组，第二个参数是这个数在数组中的下标。

在Heap.c中进行函数实现。

void AdjustUp(HpDateType* a, int child)
{
int parent = (child - 1) / 2;
while (child >= 0 && a[child] < a[parent])
{
Swap(&a[child], &a[parent]); //交换
child = parent;
parent = (child - 1) / 2;
}
}

3.3.3 push

在Heap.h中进行函数声明。

void HPPush(Heap* hp, HpDateType x);//插入

在Heap.c中进行函数实现。

void HPPush(Heap* hp, HpDateType x)
{
assert(hp);

if (hp->size == hp->capacity) //空间不够扩容
{
int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
HpDateType* tmp = (HpDateType*)realloc(hp->a, newcapacity * sizeof(HpDateType));
if (tmp)
{
perror("malloc fail!");
return;
}
hp->a = tmp;
hp->capacity = newcapacity;
}


hp->a[hp->size] = x;//插入数据
hp->size++;//更新size

//向上调整
AdjustUp(hp->a, hp->size - 1);//size-1才是子节点的下标
}

在test.c中对前面实现的所有函数进行测试。

#include "Heap.h"
void test1()
{
int a[] = { 5,2,4,7,9,1,3,8 };
Heap hp;
HPInit(&hp); //初始化
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
HPPush(&hp, a[i]); //插入数据
}
HPDestroy(&hp);//销毁
}
int main()
{
test1();
return 0;
}

运行结果和我们分析的一样。

3.4 pop 删除数据

堆里面的删除，要求的是删除堆顶的数据，也就是根位置，堆里最小的数。在小堆里，这样删除可以找到第二小的数，再删除，可以找到第三小的数..；在大堆则可以找出最大的数、第二大的数、第三大的数...这样删除才有意义。

分析一下，这里删除的就是数组最开始的数据，直接删除首元素可以吗？不可以，因为直接删除的话，父子关系就全乱了。

兄弟变父子，父子变兄弟，也会导致这不是一个堆了。

所以删除的方法就是，将根节点和最后一个叶子节点交换，删除调整后的尾节点，然后采用向下调整的算法重新排序。

这样，我们就把第二小的放到了堆顶，删除之后依旧是一个小堆。

3.4.1 向下调整

我们将向下调整的代码同样封装成一个函数，实现pop时可直接复用。

在Heap.h中进行函数声明。

void AdjustDown(HpDateType* x, int size, int parent);//向下调整

第一个参数是要调整的数组，第二个参数是数组的大小，第三个参数是父节点的下标。

在Heap.c中进行函数实现。

void AdjustDown(HpDateType* x, int size, int parent)
{
int child = parent * 2 + 1;//假设左孩子小

while (child < size && x[parent] > x[child])
{
//如果右孩子小，child为右孩子下标
if (child + 1 < size && x[child] > x[child + 1]) 
{
child++;
}

Swap(&x[parent], &x[child]);//交换
parent = child;
child = parent * 2 + 1;
}
}

3.4.2 pop

在Heap.h中进行函数声明。

void HPPop(Heap* hp); //删除

在Heap.c中进行函数实现。

void HPPop(Heap* hp)
{
assert(hp);
assert(hp->size);
Swap(&hp->a[0], &hp->a[hp->size - 1]);//首尾交换
hp->size--; //删除末节点
AdjustDown(hp->a, hp->size, 0); //向下调整
}

在test.c中对前面实现的所有函数进行测试。

void test2()
{
int a[] = { 3,4,5,8,9,7,6,10 };
Heap hp;
HPInit(&hp); //初始化
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
HPPush(&hp, a[i]); //插入数据
}
for (int i = 0; i < hp.size; i++)
{
printf("%d ", hp.a[i]);
}
printf("\n");
HPPop(&hp);
for (int i = 0; i < hp.size; i++)
{
printf("%d ", hp.a[i]);
}
printf("\n");
HPDestroy(&hp);//销毁
}

这个运行结果和我们前面分析的一样。

3.5 获取根节点数据、判空

在Heap.h中进行函数声明。

HpDateType HPTop(Heap* hp); //获取堆顶数据

bool HPEmpty(Heap* hp);//判空

在Heap.c中进行函数实现。

HpDateType HPTop(Heap* hp)
{
assert(hp);
assert(hp->size);
return hp->a[0];
}

bool HPEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}

在test.c中对前面实现的函数进行测试。

void test3()
{
int a[] = { 3,4,5,8,9,7,6,10 };
Heap hp;
HPInit(&hp); //初始化
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
HPPush(&hp, a[i]); //插入数据
}
while (!HPEmpty(&hp))
{
printf("%d ", HPTop(&hp));//把堆顶元素打印出来
HPPop(&hp); //删除堆顶数据，此时堆顶为第二小的数 
}
}

我们可以通过pop和top的配合，按顺序打印出这个堆。

这里也是更加体现出pop的价值。

4.大堆的实现

前面我们已经实现好了小堆，大堆的实现只要稍微改动两个函数即可。

大堆的向上调整。

void AdjustUp(HpDateType* a, int child)
{
int parent = (child - 1) / 2;
//while (child > 0 && a[child] < a[parent])//小堆
while (child > 0 && a[child] > a[parent])//大堆
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
}

大堆的向下调整。

void AdjustDown(HpDateType* x, int size, int parent)
{
int child = parent * 2 + 1;//假设左孩子小

//while (child < size && x[parent] > x[child])//小堆
while (child < size && x[parent] < x[child])//大堆
{
//if (child + 1 < size && x[child] > x[child + 1]) //小堆
if (child + 1 < size && x[child] < x[child + 1]) //大堆
{
child++;
}

Swap(&x[parent], &x[child]);//交换
parent = child;
child = parent * 2 + 1;
}
}

其他一律不变。

在test.c中测试一下，就用前面的测试样例。

此时，大堆的pop和top结合，就可以将这个堆倒序打印出来。

5.堆的应用

5.1 top-k问题

找出一段数据最大的前k个，或者最小的前k个。有了堆，我们不需要对整个数据排序，就能做到。

比如，找出数组a最大的前5个。

void test4()
{
int a[] = { 32,41,55,38,9,71,6,10, 11, 29, 90, 103 };
Heap hp;
HPInit(&hp); //初始化
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
HPPush(&hp, a[i]); //插入数据
}
int k = 0;
scanf("%d", &k);
while (k--)
{
printf("%d ", HPTop(&hp));
HPPop(&hp);
}
printf("\n");
}

并且效率也是非常高的。假设树的节点是N，pop的时间复杂度最坏的情况都是 $\log_{2}N$ 。

5.2 建堆

现在我们有一个数组，我们要快速对这个数组建堆，怎么实现？把我们刚刚实现的小堆或者大堆再全部实现一次吗？不是的。我们只需要用到一个函数，就是向上调整，或者向下调整。

int a[] = { 32,41,55,38,9,71,6,10, 11, 29, 90, 103 };
int n = sizeof(a) / sizeof(int);
for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");

把这个数组a看作是一个完全二叉树，从下标为1的开始，下标为0的就默认已经是堆了。

这个就是建堆。这里建的是大堆。

5.3 堆排序

堆排序就使用堆的思想来完成排序。

升序：建大堆！

降序：建小堆！

如果降序建大堆，就跟前面实现pop遇到的问题一样了，会导致关系全乱套。所以，降序我们建小堆。

建小堆，我们就可以得到最小的数。

然后把首位节点一交换。

交换之后，我们把4忽视，假装它不是这个堆里面的数据。然后不包括4在内的其他数，会向下调整，继续调整为小堆。

调整为小堆之后又得到了第二小的数，第二小的数和不包括4在内的尾节点交换，也就是倒数第二个数交换。

重复上面的步骤，最小的数，第二小的数，第三小的数...这个升序就实现了。

堆排序的效率是O(N* $\log_{2}N$ )

代码实现如下。

void HeapSort(int* a, int n)
{
//降序，建小堆
for (int i = 1; i < n; i++)//建堆
{
AdjustUp(a, i);
}
int end = n - 1; //控制“视为堆内”的数据
while (end > 0)
{
Swap(&a[0], &a[end]);//交换
AdjustDown(a, end, 0);//向下调整为小堆
end--;
}
}

升序则相反。

本次分享就到这里，我们下篇再见~

原文地址：https://blog.csdn.net/2402_82757055/article/details/144302139

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Next.js 系统性教学：深入理解缓存机制(续)
下一篇：【机器学习】基础知识：拟合度（Goodness of Fit）

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14

【数据结构】堆的概念、结构、模拟实现以及应用

1.堆的概念及结构

2.父节点和子节点的对应关系

3.小堆的实现

3.1 准备工作

3.2 初始化和销毁

3.3 push 插入数据

3.3.1 交换

3.3.1 向上调整

3.3.3 push

3.4 pop 删除数据

3.4.1 向下调整

3.4.2 pop

3.5 获取根节点数据、判空

4.大堆的实现

5.堆的应用

5.1 top-k问题

5.2 建堆

5.3 堆排序

相关文章