【数据结构】《自此，每一个想考我堆排序（Top-k问题）的面试官，下场都很尴尬【附完整代码实现】》

定义：如果有一个关键码的集合K = { ，，，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆（在左右子树中根节点也是对应的最小 / 最大）

简单来说：指的是一种特殊的基于树的数据结构，堆是一颗完全二叉树，它的底层实现是一个数组，并且将堆分为--大堆、小堆。

大堆：根节点最大的堆，或叫“大根堆”、“最大堆”。
小堆：根节点最小的堆，或叫“小根堆”、“最小堆”。

--图示：

1. 堆的特性

堆中某个节点的值总是不大于其父节点的值或者不小于其父节点的值；
堆总是一颗完全二叉树；
堆顶节点是最大的或者最小的。

2. 二叉树特性延伸

对于具有n个节点的完全二叉树，按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为 i 的节点有：

求父节点：若 i > 0，i 的位置节点的双亲序号：( i - 1 ) / 2；i = 0，i 为根节点编号，无双亲节点；（结果取整，不四舍五入）求子节点：若 2i + 1 < n，左孩子序号：2i + 1，2i + 1 >= n，则无左孩子；求子节点：若 2i + 2 < n，右孩子序号：2i + 2，2i + 2 >= n，则无右孩子。

1.2 堆的结构

--因为堆的底层实现是数组，那么它的结构与前面实现顺序表的结构基本相同。

//定义堆结构 typedef int HPDataType; typedef struct Heap { HPDataType* arr; int size; //有效数据个数 int capaicty;//空间大小 }HP;

二、堆的实现

2.1 堆的初始化、销毁

1. 初始化

--初始化与前面的顺序表、栈的初始化相同，空间指向NULL，其余变量置零。

#include "Heap.h" //初始化 void HpInit(HP* php)//也是，要改变指向的对象，取地址 { assert(php); php->arr = NULL; php->size = php->capaicty = 0; }

2. 销毁

--将经过后续操作的的堆重置为初始化状态。

#include"Heap.h" void HPDesTroy(HP* php) { assert(php); if (php->arr) { free(php->arr); } php->arr = NULL; php->size = php->capaicty = 0; }

三、堆基本功能实现

3.1 入堆

入堆，与顺序表相同，就是在堆的存储结构-->数组尾部插入数据。不同的是-->必须要保证小堆或者大堆的性质不变。

        首先定义两个节点，child（指向插入的节点）、parent（指向插入节点的父节点），由求父节点公式--（i + 1）/ 2，找到父节点。

        然后parent 与 child 比较大小，交换位置，大的作父节点，小的作子节点；child继续指向插入节点。

        重复以上操作（找父节点、比较大小）。最终，求父节点时-->（1-1）/ 2 不存在，结束。

3.1.1 额外接口实现

1. 交换父子接口

--用于实现算法思路中的比较、交换功能。由于构建的是大堆，以下全以大堆为背景进行操作。

#include "Heap.h" //交换父子算法 void Swap(int* x, int* y)//传的是地址，解引用 { int tmp = *x; *x = *y; *y = tmp; }

2. 向上调整接口

//向上调整算法 void AdjustUp(HPDataType* arr, int child) { //求父亲 int parent = (child - 1) / 2; //当child为头节点时，没有父节点，结束 while (child > 0) { //建大堆条件：> //建小堆条件: < //这里是大堆 if (arr[child] > arr[parent]) { Swap(&arr[child], &arr[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }

向上调整接口，最主要的就是循环（整个的大条件是节点为根节点时，无父节点，停止；等到节点找到了合适位置不再上调，跳出）进行寻找节点的父节点，根据比较结构进行父子调换，这样就完成节点在合适位置的移动。

3. 打印接口

--将操作过后的堆打印

//打印堆 void HPPrint(HP* php) { for (int i = 0; i < php->size; i++) { printf("%d ", php->arr[i]); } printf("\n"); }

--最终入堆接口

Heap.c #include "Heap.h" //入堆 void HPPush(HP* php, HPDataType x) { assert(php); //空间不够要增容 if (php->size == php->capaicty) { //增容 int newCapacity = php->capaicty == 0 ? 4 : 2 * php->capaicty; HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } php->arr = tmp; php->capaicty = newCapacity; } //空间足够 php->arr[php->size] = x; //向上调整 AdjustUp(php->arr, php->size); ++(php->size); } test.c #include "Heap.h" void test01() { HP hp; //初始化 HPInit(&hp); HPPush(&hp, 25); HPPush(&hp, 15); HPPush(&hp, 10); //插入80 HPPush(&hp, 80); //打印 HPPrint(&hp); //销毁 HPDesTroy(&hp); } int main() { test01(); return 0; }

3.2 出堆（堆顶操作）

操作是在堆顶操作（根节点），但是与栈等的不同之处：不能直接将顶部节点删除，这样会导致节点之间的关系乱套，堆的结构变化非常大。

图示：

观察发现，直接删除后的堆既不是大堆也不是小堆，而且父子关系发生变化，调整很麻烦。

--那既能删除根节点，有最大限度地保留中间节点的父子关系，该怎么操作呢？

：那就可以尝试将根节点与最后一个节点进行调换。

图示：

观察发现，除了根节点与尾节点的调换，其余节点的父子关系没有改变，这就在后面的向下调整就会很舒服。

3.2.1 额外接口实现

1. 向下调整接口

--接口目的：将堆重新调整为大堆或者小堆。

--算法思路：定义两个指针--p（指向10）、ch（左子节点--30）；（调整大堆）

--由公式2 i + 1求出左子节点，再+1为右节点；
--先将父节点的两个子节点比较大小（如果有两个子节点的话），选出大的子节点（30），进行父子交换（此时p仍指向10）；

循环进行2、3步。

图示：

--发现，经过调整堆重新变成大堆。

//向下调整算法 void AdjustDown(HPDataType* arr, int parent, int n)//传父节点下标、有效数据个数 { int child = parent * 2 + 1; //下面统一以大堆示范 while (child < n)//child超过n，代表没有子节点了 { //大堆结构：<，小堆结构: > if (child + 1 < n && arr[child] < arr[child + 1]) { child++; } //孩子和父亲比较 //大堆结构：>，小堆结构:< if (arr[child] > arr[parent]) { //父子调换 Swap(&arr[child], &arr[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }

比较子节点大小的条件中的-->child + 1 < n是确保右节点存在，这样再进行比较。没有右节点，直接指向左节点。

--最终出堆接口

Heap.c #include "Heap.h" //出堆（堆顶） void HPPop(HP* php) { assert(!HPEmpty(php)); Swap(&php->arr[0], &php->arr[php->size - 1]); --(php->size); //堆顶数据向下调整 AdjustDown(php->arr, 0, php->size); } test.c #include "Heap.h" void test01() { HP hp; //初始化 HPInit(&hp); //入堆 HPPush(&hp, 25); HPPush(&hp, 15); HPPush(&hp, 10); HPPush(&hp, 80); //打印 HPPrint(&hp); //出堆 HPPop(&hp); HPPrint(&hp); HPPop(&hp); HPPrint(&hp); HPPop(&hp); HPPrint(&hp); //销毁 HPDesTroy(&hp); } int main() { test01(); return 0; }

3.3 取堆顶

--只需要将堆顶数据输出，然后再出堆，直至堆为空。

Heap.c #include "Heap.h" //取堆顶 HPDataType HPTop(HP* php) { assert(!HPEmpty(php)); return php->arr[0]; } test.c #include "Heap.h" //循环取堆顶 while (!HPEmpty(&hp)) { int top = HPTop(&hp); printf("%d ", top); HPPop(&hp); }

--只展示循环取堆顶的主要代码，在前面需要入堆操作。

--根据结果，发现最后输出数值的是升序（降序），哎~这是不是堆的排序功能呢？

四、堆排序

4.1 实现排序的思考

--根据前面取堆顶的操作，在运行程序后，发现输出数值的顺序是有序的（升序或者降序）。

在前面提出一个问题——>取堆顶是的操作是堆的排序功能吗？先不管到底是不是堆的排序功能，下面先来单独实现一下排序看看效果：

实现思路 --> 由前面实现取堆顶操作的启发：

        将从测试程序中传过来的乱序数组进行接收，因为要将数组元素循环进行入堆操作，所以一并传过来的参数还有数组大小；

        在排序函数内部：因为要将数组元素入堆，所以要创建堆并初始化。在循环体内调用入堆接口完成入队操作

        在入堆操作之后，堆已经变成小堆或者大堆（这里我们就采用建大堆），再进行循环的取堆顶、出堆操作，将小堆的数值逐个存入数组-->数组就成为了升序数组。

--先预告一下，根据上面的算法实现的其实是假的堆排序，至于为什么，请看后面！

4.2 假的堆排序

test.c //假的堆排序--使用的是数据结构--堆 void HeapSort01(int* arr, int n) { HP hp;//使用堆结构 HPInit(&hp); //将乱序数值放入堆中 for (int i = 0; i < n; i++) { HPPush(&hp, arr[i]); } //取堆顶，输出升序或降序 int i = 0; while (!HPEmpty(&hp))//直到堆为空 { int top = HPTop(&hp); arr[i++] = top;//将有序的数值存入数组 HPPop(&hp); } HPDesTroy(&hp); } int main() { int arr[6] = { 30,56,25,15,70,10 }; printf("排序之前：\n"); for (int i = 0; i < 6; i++) { printf("%d ", arr[i]); } printf("\n"); HeapSort01(arr, 6); printf("排序之后：\n"); for (int i = 0; i < 6; i++) { printf("%d ", arr[i]); } return 0; }

--这段代码成功实现了排序功能，但是为什么一开始说它是假的堆排序呢？

:下面将程序与冒泡排序进行一个对比，看看是因为什么导致的加排序。

1. 类比冒泡排序

//冒泡排序--时间复杂度O（N^2） void BubbleSort(int* arr, int n) { for (int i= 0; i < n; i++) { int exchange = 0; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { exchange = 1; Swap(&arr[j], &arr[j + 1]); } } if (exchange = 0) { break; } } }

       思考冒泡排序：我们可以看到：在冒泡排序中，它是完全根据排序的算法思想编写的，没有借用任何的数据结构来辅助实现，这就是与第一种实现方案不同的地方。

         对于第一种实现方法：它使用了需要传堆结构的接口（初始化、判空、入堆、取堆顶、出堆）辅助实现的排序功能，那它就不是有效的堆排序。（向上调整接口、向下调整接口不需要传堆结构，可以使用）

        真正的堆排序：类似于冒泡排序的实现，就是使用堆结构的思想，不借助需要传堆结构的堆接口来构建排序功能.

4.3 真的堆排序

所以经上面所说，堆排序是借用的堆的算法思想，直接对数组进行原地操作。

图示：向下调整在这里建的是小堆，只演示排降序部分

        在一开始建完小堆后，就是要进行排降序数组（在数组内部原地操作），具体是-->将根节点数值与尾节点数值交换，完后尾节点下标 size - 1（因为最后一个元素为当前小堆结构的最小数值）；

        交换完后，堆结构不再是小堆，需要进行向下调整为小堆结构，在次重复调换。

        之后就是循环进行1、2步骤，循环条件是--> size > 0（size = 0 ，则表示所有元素已经完成排序）。

//真的堆排序 //堆排序————使用的是堆结构的思想 void HeapSort(int* arr, int n) { //向下调整算法——建小堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(arr, i, n); } //实现排序--升序数组 int end = n - 1; while (end > 0) { Swap(&arr[0], &arr[end]); AdjustDown(arr, 0, end);//logn end--; } } int main() { //test01(); int arr[6] = { 30,56,25,15,70,10 }; printf("排序之前：\n"); for (int i = 0; i < 6; i++) { printf("%d ", arr[i]); } printf("\n"); HeapSort(arr, 6); printf("排序之后：\n"); for (int i = 0; i < 6; i++) { printf("%d ", arr[i]); } return 0; }

五、建堆--算法实现的优劣

1. 两种调整算法的优劣

向上调整算法时间复杂度：

在入堆时，新节点在最后的位置。要实现的是，在插入新节点的基础下，维持堆的小堆或者大堆性质，就需要从新插入的节点开始一层一层循环的进行比较大小。

那么，就代表着循环的具体次数取决于节点的层数。根据公式：假设满二叉树节点总数是n个，那么节点深度为 --> h = log(n + 1) ( log以2为底， n+1 为对数)。

向上调整算法时间复杂度：

在出堆时，因为会导致堆结构混乱，就要从根节点一层一层的往下调整子节点之间的大小关系。

与向上一样，循环的具体次数取决于节点的层数。根据公式：假设满二叉树节点总数是n个，那么节点深度为 --> h = log(n + 1) ( log以2为底， n+1 为对数)。

所以时间复杂度都是O(log n)。

2. 两种调整建堆算法优劣

向上调整建堆算法时间复杂度：

向下调整建堆算法时间复杂度：

最后根据大O的渐进表示法：向上调整建堆算法时间复杂度 --> O(n*logn)，向下调整建堆算法时间复杂度 --> O(n)。

综上：向下调整建堆更优。

六、Top-k问题（面试问题）

TOP-K问题:即求数据结合中前k个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名，世界500强，富豪榜，游戏中前100的活跃玩家等。

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

1. 基本思路

--用数据集合中前k个元素来建堆：

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

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

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

比如：要寻找N个数据中的最大的K个数，先用前K个数据建小堆，那么就遍历剩余的N-K个元素与堆顶比较，比堆顶大就调换（小的出堆）再对堆结构进行调整为小堆，最终堆结构中的数值为最大的K个数。（反之寻找最小的K个数值，建大堆，比堆顶小的换）

2. 生成随机数

--既然要在N个数据中寻找K个最大的值，就需要生成一堆随机数。

void CreateNDate() { // 造数据 int n = 100000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (int i = 0; i < n; ++i) { int x = (rand() + i) % 1000000; fprintf(fin, "%d\n", x); } fclose(fin); }

--保存在新创建的文本文件中。

3. 遍历剩余数值

void TopK() { int k = 0; printf("请输入K："); scanf("%d", &k); const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen fail!"); exit(1); } //申请空间大小为k的整型数组 int* minHeap = (int*)malloc(sizeof(int) * k); if (minHeap == NULL) { perror("malloc fail!"); exit(2); } //读取文件中k个数据放到数组中 for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minHeap[i]); } //数组调整建堆--向下调整建堆 //找最大的前K个数，建小堆 for (int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(minHeap, i, k); } //遍历剩下的n-k个数，跟堆顶比较，谁大谁入堆 int data = 0; while (fscanf(fout, "%d", &data) != EOF) { if (data > minHeap[0]) { minHeap[0] = data; AdjustDown(minHeap, 0, k); } } //打印堆里的数据 for (int i = 0; i < k; i++) { printf("%d ", minHeap[i]); } printf("\n"); fclose(fout); } int main() { //CreateNDate(); TopK(); return 0; }

如果不放心输出的10个数是否是最大的，就可以再在文件中手动输入10个特别大的数，来验证程序功能。

回顾：

【数据结构入坑指南（七.1）】--《附带图解，深入解析孩子兄弟表示法：处理复杂树结构的终极方案》

【数据结构入坑指南（六）】--《从初始化到销毁：手把手教你打造健壮的队列实现》

结语：堆的秩序，是高效算法的基石。然而，下启链式二叉树的灵活世界，方见树形结构真正的魅力与威力。