前言：本章将详细介绍堆，并通过代码创建堆、实现一些堆的基本操作，最后以TopK问题为文章结尾。 By the way,咱们数据结构中的堆是一种数据结构，堆必然是完全二叉树，而系统层的堆是操作系统中管理内存的一块区域分段，注意区分开。

文章目录

• • • 1.堆的概念、性质
    • • 什么是堆：
      • 堆的性质：
    • 2.堆的代码实现和基本操作
    • • 定义堆
      • 堆的向上调整
      • 堆的向下调整
      • 堆的初始化
      • 堆的销毁
      • 堆的插入操作
      • 堆的删除操作
      • 获取堆顶的元素
      • 堆的判空
      • 堆内元素数量
      • 打印堆内元素
    • 3.TopK问题(即在N个数当中，选出最大/小的K个元素)
    • 4.源码链接

1.堆的概念、性质
什么是堆：

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆的性质：

1.堆中某个节点的值总是不大于或不小于其父节点的值；
2.堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是非线性数据结构，相当于一维数组，有两个直接后继。

文章图片

2.堆的代码实现和基本操作
定义堆

typedef int HPDataType; //定义大堆 typedef struct Heap { HPDataType* a; int size; int capacity; }HP;

堆的向上调整

从叶子节点插入一个元素后，想要继续保持堆的结构不变。从下往上，对二叉树进行调整，确保最后是小堆。

图示过程如下：
1.未进行插入新元素的堆：

文章图片

2.新元素0

文章图片

3.新元素0跟此时的父亲节点5比较，比5小，交换

文章图片

4.然后0继续和新的父亲节点2比较，比2小，交换

文章图片

5.然后0继续和新的父亲节点0进行比较，比1小，交换

文章图片

6.此时的child已经达到while (child > 0)的结束条件了，退出循环，新的小堆调整完毕。

void swap(int* px, int* py) { int tmp = *px; *px = *py; *py = tmp; }//前提：原本的堆就是小堆 void AdjustUp(int* a, int child) { int parent = (child - 1) / 2; //这里可以思考下为什么while的条件不适用parent>=0，因为parent不可能小于0 while (child > 0) {//只要插入的叶子节点比父亲节点小就进行交换，并不断进行循环，直至达到结束条件 if (a[child] < a[parent]) {swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else {break; } } }

堆的向下调整

比如当我们删除了堆顶第一个元素后，想要保持剩下的元素还是堆的结构时，可以考虑把最后一个叶子节点移动到堆顶，然后使用一次AdjustDown。

图示过程如下：
1.往堆顶插入新元素5

文章图片


文章图片

2.元素5跟左右孩子中小的那个进行比较，若比他大，就交换

文章图片

3.继续与左右孩子中小的进行比较，若更大，就交换

文章图片

4.继续比较，发现并不会比孩子节点小，跳出循环，新的小堆调整结束。

//堆从上到下进行调整(前提条件是：左右子树都是小堆) void AdjustDown(int* a, int n, int parent) { int child = 2 * parent + 1; while (child < n) {//选出左右孩子当中小的那个孩子 if (a[child + 1] < a[child]) {child++; }//从上到下，如果小的那个孩子比父亲节点还小，那就交换 if (a[child] < a[parent]) {swap(&a[child], &a[parent]); //child = parent; parent = child; child = parent * 2 + 1; } else {break; } } }

堆的初始化

这里以建立小堆为例，我们需要保证小堆的结构，这里通过自下而上进行调整。
这里提一嘴为什么建堆过程中的for循环内i初始值设置为（n-1-1）/2，首先数组最后一个元素下标是n-1,又有child=2*parent+1,带入后就是这个初始值。

void HeapInit(HP* php, int* a, int n) { assert(php); php->a = (HPDataType*)malloc(sizeof(HPDataType) * n); if (php->a == NULL) {printf("malloc fail"); exit(-1); } memcpy(php->a, a, sizeof(HPDataType) * n); //建堆，从下往上反复调用函数AdjustDown，建立小堆 for (int i = (n - 1 - 1) / 2; i >= 0; --i) {AdjustDown(php->a, n, i); } php->size = n; php->capacity = n; }

堆的销毁

直接free掉a，然后把php->a置空，并把size和capacity置0

void HeadDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->size = php->capacity = 0; }

堆的插入操作

1.先判断下空间是否满了，若满了，realloc开辟一块新的空间，没满就不需要开辟。
2.然后把新插入的元素放在最后一个叶子节点处
3.接下来与其双亲结点进行比较,如果比双亲结点小,就交换其值,一直不断重叠
4.最后如果该数据比双亲结点值大,就结束调整; 如果当child等于0,就结束调整

void HeadPush(HP* php, HPDatatype x) { assert(php); if (php->size == php->capacity) {HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * 2 * php->capacity); if (php->a == NULL) {printf("realloc fail"); exit(-1); } php->capacity *= 2; } php->a[php->size] = x; php->size++; //从下往上进行调整，保持堆的结构不变 AdjustUp(php->a, php->size - 1); }

堆的删除操作

该函数的作用是删除堆顶元素,并且不能毁坏堆结构，如果是你，你会写出怎样的代码来实现？
这里借助堆排序的思想,直接把堆顶第一个元素和堆底第一个元素交换，然后php->size减1，再调用一次自上而下的排序，因为size减1了，相当于除了原本堆顶第一个元素以外的元素进行调整。

void HeadPop(HP* php) { assert(php); assert(!HeapEmpty(php)); //这个地方太妙了 兄弟们！！！ swap(&a[0], a[php->size - 1]); php->size--; AdjustDown(php->a, php->size, 0); }

获取堆顶的元素

HPDataType HeapTop(HP* php) { assert(php); assert(!HeapEmpty(php)); return php->a[0]; }

堆的判空

bool HeadEmpty(HP* php) { assert(php); return php->size == 0; }

堆内元素数量

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

打印堆内元素

void HeapPrint(HP* php) { assert(php); for (int i = 0; i < php->size; i++) {printf("%d",php->a[i]); } }

3.TopK问题(即在N个数当中，选出最大/小的K个元素)

例：从（N）10亿个整数当中挑选最大的（K）10个，怎么做？

首先思考下建立大堆还是小堆？

答：建小堆，因为如果建大堆，最大的数可能挡在头的位置，其他9个次大的数就进不来。

接下来怎么建这个拥有10亿个整数的堆呢？

思路一：建一个拥有10亿个数的小堆，建堆的时间复杂度是O(N)，K个数选出来是O（KlogN），时间复杂度为O(N+KlogN)，这个复杂度太高了，能不能优化下？

思路二：建一个10个数的小堆，将10个数以外的数依次放入堆中，建堆的时间复杂度O(K)，找到K个数的时间复杂度为（NlogK），总时间复杂度就是O(K+N*logK)。

复现思路二的代码：

void PrintTopK(int* a, int n, int k) { HP hp; HeapInit(&hp, a, k); for (int i = k; i < n; ++i) {if (a[i] > HeapTop(&hp)) {HeapPop(&hp); HeapPush(&hp, a[i]); } } HeapPrint(&hp); HeapDestroy(&hp); }void TestTopk() { int n = 100000; int* a = (int*)malloc(sizeof(int) * n); srand(time(0)); for (size_t i = 0; i < n; ++i) {a[i] = rand() % 1000000; } //随机赋值十个最大的数 a[5] = 1000000 + 1; a[1231] = 1000000 + 2; a[531] = 1000000 + 3; a[5121] = 1000000 + 4; a[115] = 1000000 + 5; a[2335] = 1000000 + 6; a[9999] = 1000000 + 7; a[76] = 1000000 + 8; a[423] = 1000000 + 9; a[3144] = 1000000 + 10; PrintTopK(a, n, 10); }

补充下将一个顺序表整理成堆的时间复杂度推导：

文章图片

4.源码链接
https://gitee.com/linkylo/c_code_2021/tree/master/c_code_2021_9_3(Lab%EF%BC%89
【数据结构初阶|【数据结构】 堆的简单理解和代码实现】数据结构堆的代码实现和相关的TopK问题的内容到此介绍结束了，感谢您的阅读！！！如果内容对你有帮助的话，记得给我点个赞——做个手有余香的人。

推荐阅读

• 

  五味
• 

  激光能去除肥胖纹吗视频 激光能去除肥胖纹吗
• 

  原味烤肉制作方法 原味烤肉的制作方法
• 

  房间里面有老鼠怎么办
• 

  有没有好点收益高的副业项目？
• 

  年收入是指纯收入，年收入是什么意思
• 

  松下洗衣机烘干为什么出水,首先原因要搞清
• 

  读地图分析,如何读地图获取信息
• 

  3d|2千档高质价比手机推荐：骁龙870+三星屏+65W，真我真牛
• 

  刑事自诉案件的范围是什么
• 

  生理盐水洗鼻子可以预防新冠肺炎吗
• 

  胚芽燕麦粥
• 

  辰辉的寓意
• 

  健康工作远离疼痛现在要坐好
• 

  被子晒多久比较好
• 

  头孢料酒会有反应吗
• 

  鹌鹑鸟怎么养 鹌鹑鸟如何饲养
• 

  人成长分为哪些阶段
• 

  如何鉴别建兰国魂真假 如何鉴别建兰国魂真假
• 

  回归模型结果分析方法,ABC态度模型分析方法和运用

• 宽容谁
• 我要做大厨
• 增长黑客的海盗法则
• 画画吗（）
• 2019-02-13——今天谈梦想（）
• 远去的风筝
• 三十年后的广场舞大爷
• 叙述作文
• 20190302|20190302 复盘翻盘
• 学无止境，人生还很长