💯 博客内容：【数据结构】向上调整建堆和向下调整建堆的天壤之别以及堆排序算法

😀 作者：陈大大陈

🚀 个人简介：一个正在努力学技术的准前端，专注基础和实战分享，欢迎私信！

💖 欢迎大家：这里是CSDN，我总结知识和写笔记的地方，喜欢的话请三连，有问题请私信 😘 😘 😘

什么是TOPK问题？

TOPK问题的必要性和详细思路

包含TOPK算法的堆的源代码

TOPK算法复杂度分析

什么是TOPK问题？

📝TOP-K问题：在数据量比较大的情况下求数据集合中前K个最大的元素或者最小的元素，

比如：世界500强的企业、世界富豪榜、游戏中前100的氪金玩家等。

TOPK问题的必要性和详细思路

N个数寻找最大的前k个。

正常思路是把这N个数建成堆，然后 pop k次，即可找到最大的前k个值。

但是有些场景，上面的思路解决不了，比如N非常大的情况。

假设N是10亿，k是100，就不可能运行出结果。

因为如果这样建成堆的话，所占用的空间太大了。

10亿个整数需要多大的空间？答案是4GB。

4GB的内存啥电脑来了也吃不消，再说100亿，1000亿呢？

可见这不是一个可行的方法，咱们另辟蹊径。

我们知道，当数据很大时，它不会存在内存上，而是转而储存在磁盘文件里，所以我们的思路就转向磁盘文件。

磁盘中能建堆吗？答案是不能，因为磁盘不能随机访问。

解决思路，前K个数建小堆，让其它N-K个数和堆顶比较，如果比它大就替换它进堆。

替换它进堆的意思就是，将堆顶元素替换，然后将其向下调整。

最后这个小堆的内容就是最大的前K个。

向下调整算法我上篇文章介绍过，大家不了解的可以看看。

(4条消息) 【数据结构】向上调整建堆和向下调整建堆的天壤之别以及堆排序算法_陈大大陈的博客-CSDN博客

考虑到要排序的数据可能很多，我们建立一个TXT文件来存放待排序数据。

为了创建足够多的随机数，我们使用srand函数。

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

关于文件的操作，大家有忘记的可以看我之前的博客。

写程序必会的C语言文件操作（上）附手绘图详解_陈大大陈的博客-CSDN博客

运行代码。

上面我们创建了一个data文件，并且往里面存入了1000个随机数。

用上面的思路将其排序。

首先是建堆，用a中前k个元素建小堆。

然后将剩余n-k个元素依次与堆顶元素交换，不满则则替换。

替换元素之后不要忘记向下调整。

void PrintTopK(int k)
{// 1. 建堆--用a中前k个元素建小堆int* topk = (int*)malloc(sizeof(int) * k);assert(topk);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}// 读出前k个数据建小堆for (int i = 0; i < k; ++i){fscanf(fout, "%d", &topk[i]);}for (int i = (k - 2) / 2; i >= 0; --i){AdjustDown(topk, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换int val = 0;int ret = fscanf(fout, "%d", &val);while (ret != EOF){if (val > topk[0]){topk[0] = val;AdjustDown(topk, k, 0);}ret = fscanf(fout, "%d", &val);}for (int i = 0; i < k; i++){printf("%d ", topk[i]);}printf("\n");free(topk);fclose(fout);}

我们人工在data文件里面建立几个大数，运行代码。

成功打印出我们添加的几个大数，排序成功。

包含TOPK算法的堆的源代码

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<time.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
//int HeapSize(HP* php);
void Swap(HPDataType* p1, HPDataType* p2);
void HeapSort(int* a, int n);
void HeapDestroy(HP* php);
void CreateNDate();
void PrintTopK(int k); 
#define _CRT_SECURE_NO_WARNINGS
#include"heap.h"
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child+1< n && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){	Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
void HeapPop(HP* php)
{assert(php);Swap(&php->a[0], &php->a[php->size - 1]);php->size--; AdjustDown(php->a, php->size,0);
}
HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}//void HeapSort(int* a, int n)
//{
//	HP hp;
//	HeapInit(&hp);
//	for (int i = 0; i < n; i++)
//	{
//		HeapPush(&hp, a[i]);
//	}
//	int i = 0;
//	while (!HeapEmpty(&hp))
//	{
//		int top = HeapTop(&hp);
//		a[i++] = top;
//		HeapPop(&hp);
//	}
//	HeapDestroy(&hp);
//}
//换出我们想要的结构，向上建立小堆，然后删除元素，最后建立大堆 1 3 5 4 5 9 7 8
//建小队回损坏结构
//向下调整算法可以帮我们完成工作
//升序-》建大堆    降序-》建小堆void HeapSort(int* a, int n)
{int end = n-1;//向上调整建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}while (end>0){Swap(&a[0], &a[end]);AdjustDown(a,end, 0);--end;}
}
void CreateNDate()
{// 造数据int n = 1000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 10000;fprintf(fin, "%d\n", x);}fclose(fin);
}
void PrintTopK(int k)
{// 1. 建堆--用a中前k个元素建小堆int* topk = (int*)malloc(sizeof(int) * k);assert(topk);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}// 读出前k个数据建小堆for (int i = 0; i < k; ++i){fscanf(fout, "%d", &topk[i]);}for (int i = (k - 2) / 2; i >= 0; --i){AdjustDown(topk, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换int val = 0;int ret = fscanf(fout, "%d", &val);while (ret!=EOF){if (val > topk[0]){topk[0] = val;AdjustDown(topk, k, 0);}ret = fscanf(fout, "%d", &val);}for (int i = 0; i < k; i++){printf("%d ", topk[i]);}printf("\n");free(topk);fclose(fout);}
//test.c
#define _CRT_SECURE_NO_WARNINGS
#include"heap.h"
void UpSort(HPDataType* a, int n)
{for (int i = 1; i < n; i++){AdjustUp(a, i);}
}
int main()
{HP hp;HeapInit(&hp);int a[] = { 7,8,4,6,3,0,1,2,5,9 };//HeapSort(a, sizeof(a) / sizeof(a[0]));int n = sizeof(a) / sizeof(int);HeapSort(a, sizeof(a) / sizeof(a[0]));/*for (int i = 0; i < sizeof(a) / sizeof(int); ++i){HeapPush(&hp, a[i]);}while (!HeapEmpty(&hp)){printf("%d\n", HeapTop(&hp));HeapPop(&hp);}*/for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){printf("%d ", a[i]);}printf("\n");//CreateNDate();PrintTopK(5);return 0;
}