片头嗨小伙伴们大家好今天我们来深入理解堆这种数据结构分析一下堆排序以及TOP-K问题准备好了吗我要开始咯一、堆排序这里我们先假设要排成升序也就是从左到右结点的值依次增大思路一①先有堆这个数据结构②给定一个数组arr, 我们可以把arr数组里面的元素全部拷贝到堆中然后利用堆自身向下调整算法来进行排序排成小堆排好序后再逐一拷贝回arr数组。向下调整算法有一个前提左右子树必须是堆采用向下调整算法从第一个结点(下标为0)开始逐个进行比较如果子节点比父节点小则交换第一次第二次第三次好啦了解完向下调整算法后那什么是向下调整建堆呢举个例子接下来的内容可要仔细听好咯~假设我们需要建立大堆我们可以保持最后一层不动也就是叶子结点的那一层不变调整它的上一层也就是从倒数第一个叶子结点的父节点开始向下调整比较父节点的左孩子和右孩子如果孩子结点比父节点大那么交换然后比较下一个父节点和它的孩子结点。第一次最后一个节点的下标为size-1,那么它的父节点(倒数第一个非叶子结点)的下标为(size-1-1)/2 比较父节点的左孩子和右孩子第二次从倒数第一个非叶子结点依次往前找父节点也就是 (size-1-1)/2 -1 然后比较它的左孩子和右孩子此时我们比较“70”的左孩子“50”和右孩子“32”发现左右孩子都比父节点的值小因此我们不作处理继续往前寻找父节点。第三次往前找父节点也就是 (size-1-1)/2 -1 -1 我们找到了“60”这个父节点这里有一个隐藏的细节不知道大家发现了没“60”这个结点的左右子树都是大堆这时比较它的左孩子“70”和右孩子“100”发现右孩子100比左孩子大因此将父节点的值和子节点交换。第四次我们寻找“60”这个父节点的孩子结点发现它只有左孩子结点并且左孩子结点的值比父节点大因此交换OK啦我们向下调整建堆就完成啦代码如下//交换 void Swap(int* a, int* b) { int temp *a; *a *b; *b temp; } //向下调整算法小堆 void AdjustDown(ElemType* arr, int size, int parent) { assert(arr); int child parent * 2 1;//假设左孩子比右孩子小 while (child size) { //还没有遍历到叶子结点的时候进入循环 if (child 1 size arr[child 1] arr[child]) { //如果右孩子存在并且右孩子的值小于左孩子 child child 1; } if (arr[child] arr[parent]) { //如果子节点小于父节点交换 Swap(arr[parent], arr[child]); parent child;//将子节点赋给父节点 child parent * 2 1;//寻找下一个子节点 } else { //如果父节点小于子节点退出循环 break; } } } //堆的构建 void HeapCreate(Heap* hp, ElemType* a, int n) { //断言防止传入空指针 assert(hp); //断言防止传入空指针 assert(a); //将堆的动态数组arr开辟一个能存放n个元素的空间 hp-arr malloc(n * sizeof(ElemType)); if (hp-arr NULL) { //如果内存不足开辟失败 perror(malloc fail!\n); exit(1); } //将a数组里面的所有元素拷贝到堆的动态数组中 memcpy(hp-arr, a, n * sizeof(ElemType)); //堆的容量为n hp-capacity n; //堆的大小为n hp-size n; //向上调整建堆 //从下标为1的元素开始一直到下标为size-1的元素结束 /*for (int i 1; i hp-size; i) { AdjustUp(hp-arr, i); }*/ //向下调整建堆将堆里面的所有元素调整成小堆 //从最后一个结点的父节点开始一直到根节点结束 for (int i (hp-size-1-1)/2 ; i 0; i--) { AdjustDown(hp-arr, hp-size, i); } } //堆的判空 int HeapEmpty(Heap* hp) { assert(hp);//断言防止传入空指针 return hp-size 0;//判断堆的大小是否为0 } //取堆顶的数据 ElemType HeapTop(Heap* hp) { assert(hp);//断言防止传入空指针 return hp-arr[0];//获取堆顶元素 } //堆的删除 void HeapPop(Heap* hp) { assert(hp);//断言防止传入空指针 Swap(hp-arr[0], hp-arr[hp-size - 1]);//将堆顶元素和最后一个元素进行交换 hp-size--;//堆的大小减一 AdjustDown(hp-arr, hp-size, 0);//向下调整算法 } //堆的销毁 void HeapDestroy(Heap* hp) { assert(hp);//断言防止传入空指针 if (hp-arr) { //如果堆的动态数组存在那么就释放占用的内存空间 free(hp-arr); hp-arr NULL;//置空 } hp-capacity 0;//堆的容量为0 hp-size 0;//堆的大小为0 } // 对数组进行堆排序 void HeapSort(int* a, int n) { assert(a);//断言防止传入空指针 Heap hp;//创建堆这个结构体 HeapCreate(hp, a, n);//堆的创建将数组的元素全部拷贝到堆中进行堆排序 int i 0;//数组下标从0开始 while (!HeapEmpty(hp)) { //将堆里面的数据依次拷贝到数组中 a[i] HeapTop(hp); HeapPop(hp);//每拷贝完一次堆就删除堆顶元素 } HeapDestroy(hp);//堆的销毁防止内存泄漏 }测试一下#includeHeap.h int main() { int arr[] { 23,45,89,12,33,78,100 }; HeapSort(arr, sizeof(arr) / sizeof(arr[0])); for (int i 0; i sizeof(arr) / sizeof(arr[0]); i) { printf(%d , arr[i]); } return 0; }运行结果为23 45 12 33 78 89 100思路一理解起来很简单但是它有2个致命的缺陷①必须要提供堆这种数据结构②空间复杂度为O(N) ,那还有没有其他方法呢思路二①直接对数组进行向下调整建堆先排成大堆 ②再采用交换思想逐步排成小堆不过有一个小问题我想排成升序为啥不能直接建小堆呢来咱们举个例子~我们现在需要获取次小的元素于是我们把栈顶元素删除因此如果要排成升序只能选择建大堆还是arr数组我们再来画一遍图~ 这次是建大堆别忘记哈我们想要排成升序该怎么做呢很简单~ 我们现在已知最大的元素是“9”是堆顶元素下标为0最小的元素是“0”是堆底元素下标为 n-1 n代表数组arr的个数我们已知最大元素和最小元素那么就让它们交换将最大的元素放在最后接下来把最后一个数不看作堆里面也就是说堆里面原本有n个数现在把最后一个数“9”不看作堆里面现在一共有n-1个数。然后我们再开始从根节点向下调整继续调整成大堆。因为之前已经创建好大堆了因此不需要从倒数第一个非叶子结点开始向下调整第一次从下标为0的元素开始比较它的左孩子和右孩子如果其中一个子节点大于父节点就进行交换。第二次继续比较父节点和它的子节点如果其中一个子节点大于父节点就进行交换。第三次继续比较父节点和它的子节点如果其中一个子节点大于父节点就进行交换。完整过程如下OK,现在我们将剩余的元素又排成了大根堆我们继续将堆顶元素“8”和堆底元素“4”进行交换~第一次第二次第三次OK,此时已经符合大根堆也就是堆中每一个父节点都大于子节点左右子树都是大堆。完整过程如下OK,现在我们将剩余的元素又排成了大根堆我们继续将堆顶元素“7”和堆底元素“0”进行交换~后面的过程和前面一样这里就不画图了~代码如下/将数据类型int重命名为ElemType,方便以后修改 typedef int ElemType; //堆的结构体类型 typedef struct Heap { ElemType* arr; int capacity; int size; }Heap; //交换 void Swap(int* a, int* b) { int temp *a; *a *b; *b temp; } //向下调整算法大堆 void AdjustDown(ElemType* arr, int size, int parent) { assert(arr); int child parent * 2 1;//假设左孩子比右孩子大 while (child size) { //还没有遍历到叶子结点的时候进入循环 if (child 1 size arr[child 1] arr[child]) { //如果右孩子存在并且右孩子的值大于左孩子 child child 1; } if (arr[child] arr[parent]) { //如果子节点大于父节点交换 Swap(arr[parent], arr[child]); parent child;//将子节点赋给父节点 child parent * 2 1;//寻找下一个子节点 } else { //如果父节点大于子节点退出循环 break; } } } //堆排序 void HeapSort1(int* a, int n) { assert(a);//断言防止传入空指针 for (int i (n - 1 - 1) / 2; i 0; i--) { //从最后一个结点的父节点开始一直到根节点结束 AdjustDown(a, n, i);//向下调整算法调整成大堆 } //这里的n-1有2层含义 //①数组最后一个元素的下标为n-1 //②数组总共有n个数交换后将最后一个值不看作堆里面共n-1个数 int end n - 1; while (end 0) { Swap(a[0], a[end]);//将首尾元素交换 AdjustDown(a, end, 0);//向下调整算法从下标为0的元素开始 end--;//每交换完一次都要把最后一个数不看作堆里面 } }好啦堆排序的两种方法讲解完毕接下来我们继续学习TOP-K问题二、TOP-K问题TOP-K问题即求数据集合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。比如几十个几百个几千个甚至是上亿个数字中找到最大的前K个数字。对于TOP-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了甚至无法将数据放入数组。最佳的方式就是用堆来解决基本思路如下1. 用数据集合中前k个来建堆*要找最大的前k个元素建小堆*要找最小的前k个元素建大堆2. 用剩余的N - K个元素依次与栈顶元素来比较如果比堆顶的值大就替换它进堆堆整体向下调整将剩余N-K个元素依次与堆顶元素比较完毕后堆中剩余的K个元素就是所求的前K个最小或者最大的元素本次topk示例中计算的是最大的前k个。我们可以用文件操作的方法来写一个造数据的函数void CreateNDate() { //造数据 int n 10000; 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() % 1000000;//产生随机数 fprintf(fin, %d\n, x);//将产生的随机数填充到文件中 } //关闭文件 fclose(fin); }这里将造出来的数据写入到data.txt文件中运行完此函数后当前目录下会多一个data.txt文件打开此文本文件通过这个函数我们已经成功造出了10000个数据了。接下来就是topk代码的实现#define _CRT_SECURE_NO_WARNINGS 1 #includestdio.h #includestdlib.h #includeassert.h #includetime.h typedef int ElemType; //交换 void Swap1(int* a, int* b) { int temp *a; *a *b; *b temp; } //向下调整算法(建小堆) void AdjustDown1(ElemType* arr, int size, int parent) { assert(arr); int child parent * 2 1; //假设左孩子的值比右孩子小 while (child size) { //还没有遍历到叶子结点,进入循环 if (child 1 size arr[child 1] arr[child]) { //如果右孩子存在,并且右孩子的值小于左孩子 child; } //如果子节点小于父节点,交换 if (arr[child] arr[parent]) { Swap1(arr[child], arr[parent]); parent child; //将子节点赋给父节点 child parent * 2 1;//寻找下一个子节点 } else { //如果父节点小于子节点,退出循环 break; } } } void CreateNDate() { // 造数据 int n 10000; 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() % 1000000;//产生随机数 fprintf(fin, %d\n, x); //将产生的随机数写入到文件中 } //关闭文件 fclose(fin); } void PrintTopK(int k) { //打开需要查找前k个数据的文件---data.txt const char* file data.txt; FILE* fout fopen(file, r); if (fout NULL) { perror(fopen error); return; } //创建存放堆数据的空间 int* kminheap (int*)malloc(sizeof(int) * k); if (kminheap NULL)//如果空间不足,则开辟失败 { perror(malloc error); return; } //往堆里面填充k个数据 for (int i 0; i k; i) { fscanf(fout, %d, kminheap[i]); } // 建k个数据的小堆(倒数第一个非叶子结点开始向下调整) for (int i (k - 1 - 1) / 2; i 0; i--) { AdjustDown1(kminheap, k, i); } //将剩余的n-k个元素依次和堆顶元素比较,如果比堆顶的值大,就替换它进堆 int val 0; while (!feof(fout))//EOF是文件的结束标志,它的值为-1 { fscanf(fout, %d, val);//读取文件中剩余的n-k个数 if (val kminheap[0]) //如果比堆顶的元素大,就替换它进堆 { kminheap[0] val; AdjustDown1(kminheap, k, 0);//从第一个节点开始向下调整 } } //打印前k个最大的数字 for (int i 0; i k; i) { printf(%d , kminheap[i]); } printf(\n); } int main() { //CreateNDate(); int k 0; printf(请输入k的值: ); scanf(%d, k); PrintTopK(k); return 0; }运行结果如下:片尾今天我们学习了堆排序以及堆的TOP-K问题希望看完这篇文章能对友友们有所帮助求点赞收藏加关注 谢谢大家