【堆排序】 及 【Top-K问题】

博主的个人主页，点击这里~

数据结构专栏，点击这里~

一、【一周目】堆排序

1.1框架创建

上期博客，我们实现了数据结构堆，那么想必各位都听说过堆排序，这种排序方式就是利用堆这一数据结构实现的，很多人都有一种即使学过堆，仍旧感觉堆排序很深奥的错觉，因为不知道堆是如何实现堆排序的，我学完堆也不知道它是如何与堆排序产生关联的，直到接触到堆排序的内容才知道，堆排序确实是使用了堆及堆的思想，废话少说，咱们进入正题。

我们知道堆分为大根堆和小根堆两种，大根堆中堆顶的数据是所有数据中最大的，小根堆中堆顶的数据是所有数据中最小的，假设我们现在要实现升序，我们要对1、4、5、2、7进行排序，那么首先我们就要建堆，那建那种堆好呢？

我们知道出堆只能出堆顶，而且在出堆的时候，堆顶还会和最后一个元素互换位置，这样最后一个元素就是最大或者最小的了。

大家仔细回味这句话就会发现，我们已经将框架建立起来了，就是排升序用大根堆，因为每次出堆时，最大的元素(也就是堆顶)会排在末尾；排降序用小根堆，每次出堆时，最小的元素会排在末尾。

所以进行堆排序的第一步就是要建好堆，之后进行不断地出堆、调整堆就可以实现堆排序了。

1.2 储存要排序的数据

首先，我们要给出要排序的数组，并将它们存储起来，假设我们要存储n个数据，我们需要创建一个数组储存它们，其次我们还需要创建一个一摸一样的数组来给出建堆的空间。

代码：

int n;
scanf("%d", &n);
int* a = (int*)malloc(sizeof(int) * (n + 1));
int* heap = (int*)malloc(sizeof(int) * (n + 1));
int size = 0;
for (int i = 0;i < n;i++)
{scanf("%d", &a[i]);
}

1.3 建堆

这样我们就给出了要排序的数据数组a及建堆时需要的数组heap，接下来便是建堆的操作，也就是HPPush操作，这里和上期博客教的方法相同。

代码：
HPPush：

void HPPush(int* heap, int x, int* size)
{heap[*size] = x;int child = *size;int parent = (child - 1) / 2;while (child > 0){if (heap[child] > heap[parent]){Swap(&heap[child], &heap[parent]);child = parent;parent = (child - 1)/2;}else{break;}}(*size)++;
}

Swap:

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}

以上两段代码就是建堆的核心操作，Swap交换函数不用多说，HPPush就是将读取到的数据不断进行调整建堆。

建堆的剩余部分代码：

//建大根堆
for (int i = 0;i < n;i++)
{HPPush(heap, a[i],&size);
}

好了，看到这里恭喜你打败了80%的人，哈哈哈~

1.4 堆排序

接下来，就是我们的核心内容堆排序，首先端出主函数中的核心代码让大家鉴赏一二。

//堆排序
for (int i = 0;i < n;i++)
{//将大的存到目前的最后位置Swap(&heap[0], &heap[size - 1]);size--;//向下调整，保证堆一直是大根堆AdjustDown(heap, 0, size);
}

其中Swap是将我们建好堆的堆顶(最大值)和堆尾交换，然后size减一，说明我们又排好了一个元素，AdjustDown是为了将现在的堆顶放在它该在的位置，来保证堆始终是大根堆，也就是我们上期博客讲解的向下排序算法。

AdjustDown：

void AdjustDown(int* heap, int parent, int n)
{//假设左孩子最大int child = parent * 2 + 1;while (child < n){if (child + 1 < n && heap[child] < heap[child + 1]){child++;}if (heap[child] > heap[parent]){Swap(&heap[child], &heap[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

OK，写完这部分我们的堆排序就已经实现完成了，剩余的部分就是打印排列好数据。

看到这里，恭喜你打败了95%的人，哈哈哈~

1.5 打印数据

for (int i = 0;i < n;i++)
{printf("%d ", heap[i]);
}

测试结果：


看到这里，恭喜你打败了98%的人，哈哈哈~

2.1 源代码

#include <stdio.h>
#include <stdlib.h>void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void HPPush(int* heap, int x, int* size)
{heap[*size] = x;int child = *size;int parent = (child - 1) / 2;while (child > 0){if (heap[child] > heap[parent]){Swap(&heap[child], &heap[parent]);child = parent;parent = (child - 1)/2;}else{break;}}(*size)++;
}void AdjustDown(int* heap, int parent, int n)
{//假设左孩子最大int child = parent * 2 + 1;while (child < n){if (child + 1 < n && heap[child] < heap[child + 1]){child++;}if (heap[child] > heap[parent]){Swap(&heap[child], &heap[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}int main()
{int n;scanf("%d", &n);int* a = (int*)malloc(sizeof(int) * (n + 1));int* heap = (int*)malloc(sizeof(int) * (n + 1));int size = 0;for (int i = 0;i < n;i++){scanf("%d", &a[i]);}//建大根堆for (int i = 0;i < n;i++){HPPush(heap, a[i],&size);}//堆排序for (int i = 0;i < n;i++){//将大的存到目前的最后位置Swap(&heap[0], &heap[size - 1]);size--;//向下调整，保证堆一直是大根堆AdjustDown(heap, 0, size);}for (int i = 0;i < n;i++){printf("%d ", heap[i]);}return 0;
}

2.2 堆排序时间复杂度分析

这里我们借助AI工具进行辅助。

建堆的时间复杂度分析：

排序的时间复杂度分析：

因此总的时间复杂度为：

2.3 稳定性与空间复杂度

• 稳定性：堆排序是不稳定的排序算法（例如，相同元素可能被交换顺序）。
• 空间复杂度：堆排序是原地排序算法，空间复杂度为 O(1)。

堆排序的O(nlogn)的效率使堆排序成为大规模数据排序的优选算法之一。

看到这里，恭喜你学会了堆排序，打败了100%的人，哈哈哈~

二、【二周目】Top-K问题

假设你现在在面试，你的面试官现在给你出了一个刁钻的题目，题目是这样的：先给你几个GB数据的文件夹，然后要求你写一个程序找出数据中排名前K个数据，要求程序的大小控制在几KB。
注：1GB = 1024MB = 1024*1024KB = 1024*1024*1024字节。10亿个整型数据大概是4个G。

那么，遇到这种问题，你又要如何解决呢？
首先肯定不能定义这么大的数组，它肯定不是几个KB能够装的下的，更别提之后对这些数据进行排序了，那么不能定义这么大的数组，怎么找出前K个数据呀，这又不是求最大值，求最大值的话肯定能够实现，我们只需要定义一个变量max，并初始化为0，从文件中取出依次比较即可，最后比较完成后max就是最大值了。

欸，你们有没有发现取最大值的思路我们可以运用一下，我们可以首先取出K个数据，然后将这K个数据按照某种顺序排好，然后我们依次从文件中取出数据进行比较，最后我们让这K个数据就是前K个数据，不就行了？！

此时聪明的读者就发现了，这不就是堆结构的雏形吗？

我们可以建立一个大根堆或者小根堆，然后让处于最大值或最小值的堆顶和从文件中取出的数据进行比较，不就能不断将大或者小的数据储存在堆中吗？
不错，这道面试题的解法就是这样。

假设我们取数据中最大的前K个数据：

我们应该建立的是小根堆。为什么？

因为堆顶永远是排在第K位的数据，其它的都比堆顶大，这样我们将整个文件中的数据比较完，这个堆中储存的就是最大的前K个数据！

好了，看到这里，恭喜你打败了50%的人，哈哈哈~

1.1 创建数据文件

那么我们首先第一步就是要创建数据文件，化身刁钻的面试官，桀桀桀~

代码：

void creatdata()
{int n = 30000;FILE* file = fopen("data.txt", "w");if (file == NULL){perror("fopen fail!");return 1;}for (int i = 0;i < n;i++){int r = rand() % 100000;fprintf(file, "%d\n", r);}fclose(file);
}

这里的文件操作，和生成随机数操作在之前的博客中亦有记载！
生成随机数相关博客
文件操作相关博客
生成效果：

可以看出这里已经生成好了30000个数据，为了我们最后得出的结果更有辨识度，这里我要求生成的30000个数据小于100000，我们在从中删除10个数据，将他们替换成1000001、1000002、1000003、1000004、1000005、1000006、1000007、1000008、1000009、1000010这样当程序运行结束后我们就可以判断程序是否真的起作用了。

看到这里，恭喜你打败了85%的人，哈哈哈~

1.2 建立大小为K的小根堆

这里我们和上期博客的方法类似，当堆中数据没有达到K个时我们入堆并向上调整建堆。

if (size < k)
{heap[size] = x;AdjustUp(heap, size);size++;
}

AdjustUp：

void AdjustUp(int* heap, int child)
{int parent = (child - 1) / 2;while (child > 0){if (heap[child] < heap[parent]){Swap(&heap[child], &heap[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

Swap：

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}

好了，看到这里，恭喜你建立了小根堆，打败了95%的人，哈哈哈~

1.3 比较替换堆中元素

这里也是代码的核心部分，我们现在已经建立起了小根堆，此时堆顶是堆中的最小值，如果我们遇到比堆中最大值还大的数据，那我们也要更换堆顶，因为它是堆中的最小值。

这里代码的操作就是遇到比堆顶大的，就将堆顶替换掉，并进行向下调整，保证堆顶依旧是最小值。

代码：

else if(x > heap[0])//建堆完成后
{heap[0] = x;AdjustDown(heap, 0, k);
}

AdjustDown：

void AdjustDown(int* heap, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && heap[child] > heap[child + 1]){child++;}if (heap[child] < heap[parent]){Swap(&heap[child], &heap[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

Swap：

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}

看到这里，你成功解决了Top-K问题，恭喜你打败了99.8%的人，hahaha~

1.4 打印输出结果

for (int i = 0;i < k;i++)
{printf("%d ", heap[i]);
}

运行结果：

果然如此吗，和我们预期的结果一样，恭喜你解决了问题，打败了100%的人，哈哈哈，咳咳。

2 、源代码

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include<stdlib.h>
#include<time.h>void creatdata()
{int n = 30000;FILE* file = fopen("data.txt", "w");if (file == NULL){perror("fopen fail!");return 1;}for (int i = 0;i < n;i++){int r = rand() % 100000;fprintf(file, "%d\n", r);}fclose(file);
}void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void AdjustUp(int* heap, int child)
{int parent = (child - 1) / 2;while (child > 0){if (heap[child] < heap[parent]){Swap(&heap[child], &heap[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void AdjustDown(int* heap, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && heap[child] > heap[child + 1]){child++;}if (heap[child] < heap[parent]){Swap(&heap[child], &heap[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}int main()
{//srand((unsigned int)time(NULL));//creatdata();//这里注释掉因为建立一次数据文件就够了int k = 10;int* heap = (int*)malloc(sizeof(int) * (k + 1));int size = 0;FILE* file = fopen("data.txt", "r");if (file == NULL){perror("fopen fail!");return 1;}int x = 0;while (fscanf(file, " %d", &x) != EOF){if (size < k){heap[size] = x;AdjustUp(heap, size);size++;}else if(x > heap[0])//建堆完成后{heap[0] = x;AdjustDown(heap, 0, k);}}for (int i = 0;i < k;i++){printf("%d ", heap[i]);}fclose(file);return 0;
}

总结：
以上就是本期博客分享的全部内容啦！如果觉得文章还不错的话可以三连支持一下，你的支持就是我前进最大的动力！
技术的探索永无止境! 道阻且长，行则将至！后续我会给大家带来更多优质博客内容，欢迎关注我的CSDN账号，我们一同成长！
(～￣▽￣)～