从零实现数据结构：堆的实现和简单堆排序

🕗 发布于 2024-10-18 11:57 数据结构 c语言 算法

事先说明，这里采用的都是小堆。下面是代码中的小堆示意图

这里向大家分享一个常见数据结构可视化的网址：Data Structure Visualization (usfca.edu)

声明部分heap.h：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int HPDataType;

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

void HeapInit(hp* hp);
void HeapDestroy(hp* hp);
bool HeapEmpty(hp* hp);
HPDataType Heaptop(hp* hp);
int HeapSize(hp* hp);
void swap(HPDataType* x, HPDataType* y);
void AdjustUp(HPDataType* a, int child);
void HeapPush(hp* hp, HPDataType data);
void AdjustDown(HPDataType* a, int n);
void HeapPop(hp* hp);

函数实现部分heap.c：

初始化函数：

void HeapInit(hp* hp)
{
assert(hp);
hp->a = NULL;
hp->capacity = hp->size = 0;
}

销毁函数：

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

判空函数：

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

返回top元素函数：

HPDataType Heaptop(hp* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
return hp->a[0];
}

返回size函数：

int HeapSize(hp* hp)
{
assert(hp);
return hp->size;
}

交换函数：

void swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}

向上调整函数：

void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[parent] > a[child]) // 小于关系确保最小堆
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}

由于前面的代码比较简单，就不再做过多解释。这里注重讲解一下为什么要向上调整，以及这个思路是怎么来的。这里还是拿开头那个例子来举例：

当我们插入一个新的0的时候，这个时候就已经不满足小堆的定义了，我们需要对堆进行调整。

由于小堆要求父节点比所有的子节点都小，所以很自然的想法就是向上和父节点进行交换。你可能会问为什么不和其他的结点相比较，这是因为我们的目标是动最少的元素来完成，如果和其他结点进行交换剩下结点的父子关系就全部乱掉了，因此在不打乱其他结点的父子关系的唯一做法就是和自己的父节点进行比较。

当我们交换完成之后，发现依然不满足小堆的定义，所以很自然的想法是继续与父节点交换，然后向上调整的雏形就已经被我们构想出来了。

插入函数：

void HeapPush(hp* hp, HPDataType data)
{
assert(hp);
if (hp->capacity == hp->size)
{
int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->a, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
hp->a = tmp;
hp->capacity = newcapacity;
}
hp->a[hp->size] = data;
AdjustUp(hp->a, hp->size);
hp->size++;
}

向下调整函数：

void AdjustDown(HPDataType* a, int n)
{
int parent = 0;
int leftchild = 2 * parent + 1;

while (leftchild < n) // 确保左孩子在范围内
{
int minchild = leftchild;
int rightchild = leftchild + 1;

if (rightchild < n && a[rightchild] < a[leftchild])
{
minchild = rightchild; // 找到较小的子节点
}

if (a[parent] > a[minchild]) // 小于关系确保最小堆
{
swap(&a[parent], &a[minchild]);
parent = minchild;
leftchild = 2 * parent + 1; // 更新为新的左孩子
}
else
{
break;
}
}
}

同理这里向下调整也是一样，需要注意的是这里的写法，我们先是假设左边的结点是小的，然后再用判断。如果不这样做，则需要将父节点和两个子节点进行比较，这样会造成多余的比较次数。

还需要注意的是这行逻辑

if (rightchild < n && a[rightchild] < a[leftchild])

这里的逻辑是堆是完全二叉树，即使左节点存在右节点也有可能不存在，所以需要判断是否越界，并且这里的两个判断不能调换顺序，因为一旦交换，你就先越界访问了再进行的判断已经没有用了。

删除函数：

void HeapPop(hp* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
swap(&hp->a[0], &hp->a[hp->size - 1]); // 交换根和最后一个元素
hp->size--;
AdjustDown(hp->a, hp->size);
}

你可能还是会问为什么要一开始和根节点进行交换然后再进行调整，这还是因为我们的目标是动最少的元素完成。首先我们不能前后移动元素，因为一旦移动所有节点的父子关系就全部乱了，很有可能不满足原来的大堆或者小堆的定义了，所以我们能做的就只有交换元素。于是为了更少的交换我们直接和根结点进行交换。

还是举上面的例子来说明删除的逻辑：

原来的状态：

交换头尾元素：

比较大小，进行调整：

重复向下调整：

因此根据示意图，我们可以发现不管是向上调整还是向下调整都是最多调整高度次，按照二叉树的性质，实现复杂度也都是log2N.

完整实现代码：

#define _CRT_SECURE_NO_WARNINGS
#include "heap.h"
#include <assert.h>
#include <stdbool.h>


void HeapInit(hp* hp)
{
assert(hp);
hp->a = NULL;
hp->capacity = hp->size = 0;
}

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

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

HPDataType Heaptop(hp* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
return hp->a[0];
}

int HeapSize(hp* hp)
{
assert(hp);
return hp->size;
}

void swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}

void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[parent] > a[child]) // 小于关系确保最小堆
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}

void AdjustDown(HPDataType* a, int n)
{
int parent = 0;
int leftchild = 2 * parent + 1;

while (leftchild < n) // 确保左孩子在范围内
{
int minchild = leftchild;
int rightchild = leftchild + 1;

if (rightchild < n && a[rightchild] < a[leftchild])
{
minchild = rightchild; // 找到较小的子节点
}

if (a[parent] > a[minchild]) // 小于关系确保最小堆
{
swap(&a[parent], &a[minchild]);
parent = minchild;
leftchild = 2 * parent + 1; // 更新为新的左孩子
}
else
{
break;
}
}
}

void HeapPush(hp* hp, HPDataType data)
{
assert(hp);
if (hp->capacity == hp->size)
{
int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->a, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
hp->a = tmp;
hp->capacity = newcapacity;
}
hp->a[hp->size] = data;
AdjustUp(hp->a, hp->size);
hp->size++;
}

void HeapPop(hp* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
swap(&hp->a[0], &hp->a[hp->size - 1]); // 交换根和最后一个元素
hp->size--;
AdjustDown(hp->a, hp->size);
}

测试部分test.c：

#define _CRT_SECURE_NO_WARNINGS
#include "heap.h"

int main()
{
hp heap;
HeapInit(&heap);
int arr[] = {0,1,3,2,5,6,7,4};
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
HeapPush(&heap, arr[i]);
}
while (!HeapEmpty(&heap))
{
printf("%d ", Heaptop(&heap));
HeapPop(&heap);
}
return 0;
}

其实根据堆的定义来讲，即使你已经建好了小堆，但是仍然和有序存在一定距离，小堆唯一满足的有序就是根节点是最小的，所以我们如果要按照升序输出就只能先按照小堆建立，然后删除根结点再进行调整，这时根结点就已经是第二小的元素了，依次类推就拿到了升序的输出。

上面我们讲解了如何建一个大堆或者小堆，那么这里我们需要思考的问题就是如何拿到一个集合中，前k个最大的元素。例如我们要在10000个数中找到前10个最大的数，同时这也是下文所探讨的问题。

你可能会说：直接排个序，从大到小降序排下来前几名不就是TOPK了嘛

但是一般topk问题的使用环境都是大量甚至海量的数据中挑出最大的那么几十个甚至几个，这样的应用有很多，例如各种各样的排行榜就是如此。如果数据量大到一定的量级，无法一次性将所有的数据放入内存中进行比较，而且如果只是为了几个元素排所有元素的序就会造成很大量的计算资源浪费。所以在我们学习了大堆之后，就有了一个想法，那就是大堆的根结点是目前插入的元素中最大的。于是很自然的想法就是让这一万个数据一次插入建堆，每一次插入都能找到最大的数，插入完成之后，再进行pop九次就拿到了前十个最大的数。

但是这里我们既然都想到这了，就从看起来最笨的堆排序开始实现。

void HeapSort(int* a, int n)
{
hp heap;
HeapInit(&heap);
for (int i = 0; i <n; i++)
{
HeapPush(&heap, a[i]);
}
int i = 0;
while (!HeapEmpty(&heap))
{
int top = Heaptop(&heap);
a[i++] = top;
HeapPop(&heap);
}
HeapDestroy(&heap);
}

int main()
{
hp heap;
HeapInit(&heap);
int arr[] = {0,1,3,2,5,6,7,4};
HeapSort(arr, sizeof(arr) / sizeof(int));
for (int i = 0; i < sizeof(arr) / sizeof(int);i++)
{
printf("%d ", arr[i]);
}
return 0;
}

我们可以看到的确是降序输出了，由于上一集我们采用的是小堆，而今天使用的是大堆，所以我们只需要将向上调整和向下调整的<>大于小于符号交换一下就能实现将大小堆互换。由此我们也可以看出堆排序的时间复杂度为n*logn。

但是我们可以看到这里的实现方式有点繁琐多余，我们需要另一个空间建堆，建完之后然后再重新拷贝到原数组，既消耗时间又消耗空间，于是我们想能不能直接在原数组上动手。

然后我们思考如何实现，于是我们再一次地从堆的本质出发，我们这里所谓的堆实际上在物理内存上的储存形式依旧还是数组，只不过我们将数组的下标和元素大小关系进行了一定规律的映射，从而达到逻辑上是一颗完全二叉树，物理上是一个数组的效果。于是这里又分出两种不同的建堆思路，一种是向上调整建堆，一种是向下调整建堆，我们依次来思考如何实现。

因此我们在这里就当在原数组上重新建一次堆，当我们拿到我们原来的数组时，我们就当这已经是一个堆了，只不过还需要进行向上调整而已。我们从第一个元素开始依次进行向上调整的操作，当我们只有一个元素的时候已经满足了大堆的定义了，当我们有第二个元素的时候不一定满足就向上调整，以此类推，当循环到数组末尾的时候，该数组已经完成了建堆的过程。接下来就是向下交换元素，于是我们有了实现：

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/heixiu_heixiuhei/article/details/142859782

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

上一篇：前端如何在生成环境下实现自动检测更新
下一篇：webAPI中的排他思想、自定义属性操作、节点操作（配大量案例练习）

FPGA实现PCIE与电脑端QT上位机双向数据传输，基于XDMA中断模式，提供3套工程源码和技术支持
FPGA实现PCIE与电脑端QT上位机双向数据传输，基于XDMA中断模式，提供9套工程源码和技术支持
阅读更多2024-10-18
SpringBoot智能物流管理系统开发指南
在概念模式的设计中，E-R模型法是最常见的设计方法。B/S架构的运行方式是在远程的服务器上把开发的软件系统部署在远程的服务器上，在部署好软件系统之后就可以实现在任何接入互联网的电脑上访问部署好的软件系
阅读更多2024-10-18
docker删除容器要怎么操作？如何保障容器安全！
攻击者使用越来越多的高级技术入侵容器，而供应链攻击是云原生安全面临的较大问题，恶意镜像比较容易构造，绕过杀软的静态检测。可以清晰地盘点工作负载本身的相关信息，此外，还能够实现不同工作负载之间的关系可视
阅读更多2024-10-18
html5的简单问题
语义化更好的内容元素；cookies是网站为了标示用户身份而存储在用户本地终端上的数据，cookies数据始终在同源的http请求中携带，在浏览器和服务器间来回传递。导致回流现象的操作：添加或删除可见
阅读更多2024-10-18
uniapp-vue3-vite 搭建小程序、H5 项目模板
搭建一个使用和的小程序与 H5 项目模板相对简单，下面将详细介绍步骤，包括环境配置、项目创建、代码结构和基本示例。
阅读更多2024-10-18
python2与python3之间的区别
Python 2 和 Python 3 之间存在许多重要的区别。
阅读更多2024-10-18
EtherCAT总线轴实际速度和实际转矩滤波(一阶低通滤波器和TD跟踪微分器滤波对比测试)
.....
阅读更多2024-10-18
宝塔面板+HYBBS搭建私有BBS结合内网穿透一键发布论坛至公网访问
本文主要为大家介绍，如何使用HYBBS在Ubuntu系统上搭建一个好看、轻巧且扩展功能强大的论坛网站，并结合内网穿透工具发布公网随时远程访问。在国内互联网刚刚起步时，网民上网大多数时候只能浏览门户网站
阅读更多2024-10-18
自动驾驶系列—CI在自动驾驶开发中的应用场景与实现详解
随着自动驾驶技术的迅猛发展，现代车辆变得越来越智能化。越来越多的车辆功能和特性不再依赖于硬件，而是通过软件来实现。这使得自动驾驶系统的开发变得更加复杂，尤其是需要频繁更新的自动驾驶算法和控制逻辑。在如
阅读更多2024-10-18
Android打开Activity时不自动弹出键盘
在一个页面有2个EditText输入框，刚进入activity的时候系统默认第一个EditText获得焦点且键盘弹出。只需要到配置文件增加以下配置即可。这里分2种情况处理。
阅读更多2024-10-18

从零实现数据结构：堆的实现和简单堆排序

相关文章