当前位置： 首页 > news >正文

数据结构--堆的实现

news 2025/7/10 12:59:15

目录

一、堆的概念及结构

二、小根堆的实现

2.1 堆的数据结构

2.2 堆的初始化HeapInit

2.3 堆的销毁HeapDestory

2.4 堆的插入HeapPush

​2.4.1 插入代码HeapPush

2.4.2 向上调整代码AdjustUp

2.4.3 交换数据代码Swap

2.5 堆的删除HeapPop

2.5.1 删除代码HeapPop

2.5.2 向下调整算法AdjustDown

2.6 取堆顶的数据HeapTop

2.7 获取堆的数据个数HeapSize

2.8 堆的判空HeapEmpty

三、堆的应用

3.1 堆排序

3.2 TOP-K问题

3.2.1 创建大量数据

3.2.2 求K个最大的元素

3.2.3 验证

四、代码

4.1 堆的代码

4.1.1 Heap.h

4.1.2 Heap.c

4.2 堆排序的代码

4.3 TOP-K的代码

一、堆的概念及结构

堆（Heap）是一种特殊的数据结构，通常以完全二叉树的形式呈现。

堆的核心特性是：

  • 对于大根堆，任意父节点的值都大于或等于其子节点的值
  • 对于小根堆，任意父节点的值都小于或等于其子节点的值

堆通常使用数组来模拟完全二叉树的结构。数组索引按照从上到下、从左到右的方式对应树的节点排列。假设某个节点在数组中的位置为i，则其左子节点和右子节点的位置分别为 2*i+1和 2*i+2，而其父节点的位置为(i-1)/2。

如下所示：

二、小根堆的实现

2.1 堆的数据结构

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

2.2 堆的初始化HeapInit

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

2.3 堆的销毁HeapDestory

// 堆的销毁
void HeapDestory(Heap* php) {assert(php);free(php->a);php->capacity = php->size = 0;
}

2.4 堆的插入HeapPush

假如，我们现在有一个数组a:15 18 19 25 28 34 65 49 27 37，他从逻辑上看，是一个小根堆结构，我们将它的逻辑结构画出来如下所示：

我们现在想要将10插入堆里面去，插入10之后，要不允许破坏原本小根堆的结构，所以我们就需要将10一步一步的调整，如下所示：

2.4.1 插入代码HeapPush

// 堆的插入
void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->capacity == php->size) {int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("HeapPush()::realloc");exit(1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

2.4.2 向上调整代码AdjustUp

//向上调整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}

2.4.3 交换数据代码Swap

//交换函数
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}

2.5 堆的删除HeapPop

堆的删除，我们首先要确定删除哪一个元素，看上面的数组a:10 15 19 25 18 34 65 49 27 37 28.我们画出他的二叉树表现形式，如下所示，他满足小根堆特性。

 现在数组中有这么多的元素，我们要删除哪一个呢？最常见的是删除第一个元素和最后一个元素，如果我们删除最后一个元素28，删除的没有意义，他既不是最大的也不是最小的，所以堆的删除一般都是删除堆顶元素，也就是以一个元素，删除堆顶元素之后，后面的元素需要向前移动吗？答案是不能，如果向前移动，元素之间的逻辑关系会改变，不满足小堆特性，所有如果我们要删除第一个元素，通常做法是将最后一个元素与第一个元素互换，只有第一个元素不满足小根堆的特性，其他元素都满足，我们还需要写一个向下调整算法。

2.5.1 删除代码HeapPop

// 堆的删除
void HeapPop(Heap* php) {assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, 0, php->size);
}

2.5.2 向下调整算法AdjustDown

void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}

2.6 取堆顶的数据HeapTop

// 取堆顶的数据
HPDataType HeapTop(Heap* php) {assert(php);assert(php->size > 0);return php->a[0];
}

2.7 获取堆的数据个数HeapSize

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

2.8 堆的判空HeapEmpty

// 堆的判空
int HeapEmpty(Heap* php) {return php->size == 0 ? 1 : 0;
}

三、堆的应用

3.1 堆排序

如果我们想要升序的话，就需要建立大根堆。

如果我们想要降序的话，就需要建立小根堆。

现在我们有一个数组a{ 27,15,19,18,28,34,65,49,25,37 };我们想要将a进行从小到大排序，所以我们就需要对这个数组进行建堆处理。

那现在我们如何建堆呢？

方法一：我们可以访问数组的每一个元素，然后初始化一个堆，将数组的每一个元素插入到堆里面，我们根据堆的自动调整算法，可以自动的变成大根堆,然后我们取出堆顶的元素，把它放在数组里面，然后堆的删除，重复n次。但是这样空间复杂度太高了需要重新新建一个堆。

方法二：我们可以从数组的第二个元素开始，进行向上调整算法，就这个数组变成一个堆，如下所示：

for (int i = 1; i < size; i++) {AdjustUp(a, i);
}

我们打开我们的调试，看到数组a成功的变成了一个大根堆。但是这样时间复杂度太高了。

方法三：可以从最后一个分支节点开始，依次进行向下调整算法，如下所示：

for (int i =(size-2)/2 ; i >= 0; i--)//
{AdjustDown(a, i, size);
}

我们常用的建堆算法是方法三。 

建完堆之后，我们将堆顶元素与最后一个元素互换，然后重新调整堆，重复n次。代码如下所示：

int end = size - 1;
while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;
}

这样我们就成功的将数组a从小到大排序了。

3.2 TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆

        前k个最大的元素，则建小堆

        前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

        将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

3.2.1 创建大量数据

我们使用代码创建大量的数据，如下所示：

void CreatData() {FILE* pf = fopen("data.txt", "w");if (pf == NULL) {perror("fopen");exit(1);}int num = 100000;for (int i = 0; i < num; i++) {int number = rand()+i;fprintf(pf, "%d\n", number);}
}

3.2.2 求K个最大的元素

首先，输入k的值，malloc出k个int类型的空间，然后从文件中读取前k个数，将他们放在malloc出来的空间里面，将他们建成小堆，最后依次读取文件中后n-k个，依次与堆顶进行比较，如果大于堆顶就替换，然后调整堆。代码如下：

void TOP_K() {printf("请输入k：");int k = 0;scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL) {perror("malloc fail");exit(1);}//从文件中拷贝k个数到堆里面FILE* pf = fopen("data.txt", "r");if (pf == NULL) {perror("fopen");exit(1);}for (int i = 0; i < k; i++) {fscanf(pf, "%d", &kminheap[i]);}//建立k个数的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(kminheap, i, k);}//读取剩下的n-k个数据int x = 0;while (fscanf(pf,"%d", &x)>0) {if (x > kminheap[0]) {kminheap[0] = x;AdjustDown(kminheap, 0, k);}}printf("最大的前%d个数", k);for (int i = 0; i < k; i++) {printf("%d ", kminheap[i]);}printf("\n");
}

3.2.3 验证

我们现在已经把最大的前k个输出了，我们如何验证这k个元素就是十万个数据中最大的前10个呢？

我们在创建数据的时候可以%10000000，来控制我们的数据，创建完成数据之后，我们在data.txt文档中随机的修改k个数，在它们后面加上4个0，这样我们就知道k个最大的数后面肯定有4个0。我们调用top-k函数，如下所示：

可以看到最大的10个数后面都带有4个0，说明我们所写的top-k算法没有问题。

四、代码

4.1 堆的代码

4.1.1 Heap.h

#pragma once
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;
void AdjustDown(HPDataType* a, int parent, int size);
void AdjustUp(HPDataType* a, int child);
//交换函数
void Swap(HPDataType* x, HPDataType* y);
void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

4.1.2 Heap.c

#include"Heap.h"
void HeapInit(Heap* php) {assert(php);php->a = NULL;php->capacity = php->size = 0;
}
// 堆的销毁
void HeapDestory(Heap* php) {assert(php);free(php->a);php->capacity = php->size = 0;
}
//交换函数
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
//向上调整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}
}
// 堆的插入
void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->capacity == php->size) {int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("HeapPush()::realloc");exit(1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] > a[child]) {child++;}if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
// 堆的删除
void HeapPop(Heap* php) {assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, 0, php->size);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* php) {assert(php);assert(php->size > 0);return php->a[0];
}
// 堆的数据个数
int HeapSize(Heap* php) {assert(php);return php->size;
}
// 堆的判空
int HeapEmpty(Heap* php) {return php->size == 0 ? 1 : 0;
}

4.2 堆排序的代码

//交换函数
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
//向上调整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] > a[child]) {child++;}if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
void HeapSort(int* a, int size) {for (int i =(size-2)/2 ; i >= 0; i--)//{AdjustDown(a, i, size);}int end = size - 1;while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;}
}
int main() {int a[] = { 27,15,19,18,28,34,65,49,25,37 };int size = sizeof(a) / sizeof(a[1]);HeapSort(a, size);for (int i  = 0; i < size; i++) {printf("%d ", a[i]);}return 0;
}

4.3 TOP-K的代码

//交换函数
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
void CreatData() {FILE* pf = fopen("data.txt", "w");if (pf == NULL) {perror("fopen");exit(1);}int num = 100000;for (int i = 0; i < num; i++) {int number = (rand()+i)%10000000;fprintf(pf, "%d\n", number);}
}
void TOP_K() {printf("请输入k：");int k = 0;scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL) {perror("malloc fail");exit(1);}//从文件中拷贝k个数到堆里面FILE* pf = fopen("data.txt", "r");if (pf == NULL) {perror("fopen");exit(1);}for (int i = 0; i < k; i++) {fscanf(pf, "%d", &kminheap[i]);}//建立k个数的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(kminheap, i, k);}//读取剩下的n-k个数据int x = 0;while (fscanf(pf,"%d", &x)>0) {if (x > kminheap[0]) {kminheap[0] = x;AdjustDown(kminheap, 0, k);}}printf("最大的前%d个数", k);for (int i = 0; i < k; i++) {printf("%d ", kminheap[i]);}printf("\n");
}
int main() {srand((unsigned int)time(NULL));CreatData();TOP_K();return 0;
}

http://www.lryc.cn/news/583381.html

相关文章：

  • 【04】MFC入门到精通——MFC 自己手动新添加对话框模板 并 创建对话框类
  • 【PDF提取内容改名】批量提取pdf多个指定区域内容到excel表格的操作步骤和方法
  • 专题：2025母婴行业洞察报告|附60+份报告PDF汇总下载
  • Context Engineering：从Prompt Engineering到上下文工程的演进
  • React、Vue、Angular的性能优化与源码解析概述
  • 深度学习 必然用到的 微积分知识
  • RAG实战之dify源码文件解析-pdf文件解析流程
  • 【Oracle报错】[INS-13001] 环境不满足最低要求。
  • 什么是幂等
  • 【03】MFC入门到精通——MFC 添加控件 设置属性 按钮 文本框
  • 第四节 chatPDF
  • 神经网络基础及API使用详解
  • 机器学习（西瓜书） 第四章 决策树
  • 通用游戏前端架构设计思考
  • 自动化测试报告优化：jenkins+jmeter定制化HTML报告生成
  • skywalking-agent-docker镜像
  • 方差、协方差和协方差矩阵
  • Windows 10/11新系统跳过强制联网激活和注册微软账户
  • JavaScript数组键值去重方法
  • 【C++】容器适配器 + stack/queue/deque详解
  • EFK9.0.3 windows搭建
  • Ubuntu连接不上网络问题(Network is unreachable)
  • ubuntu环境下调试 RT-Thread
  • windows部署多实例filebeat监控相同路径下文件
  • 【Kafka】登录日志处理的三次阶梯式优化实践：从同步写入到Kafka多分区批处理
  • SAP-ABAP：SAP中DELECT语句用法详解实例总结
  • Go语言Gin框架实战：开发技巧
  • 2024 睿抗编程技能赛——省赛真题解析（含C++源码）
  • 【Python】遇到 “non-integer arg 1 for randrange() ” 问题的解决方法
  • 技术开发栈中 URL地址末尾加不加 “/“ 有什么区别？