【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

文章目录

前言

👧个人主页：@小沈熬夜秃头中୧⍤⃝❅
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：数据结构
🔑本章内容：堆排序+TOP-K问题
送给各位💌：日落跌入昭昭星野 人间忽晚 山河以秋
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~

提示：以下是本篇文章正文内容，下面案例可供参考

🌟一、建堆的两种方式：

🌏1.1 向上调整建堆(堆排序)：

💫1.1.1 完整代码：

//Heap.h#include<stdio.h>#include<assert.h>#include<stdlib.h>#include<stdbool.h>typedefint HPDataType;typedefstructHeap{
    HPDataType* a;int size;int capacity;}HP;voidAdjustDown(int* a,int n,int parent);//因为要在Test.c中调用这个函数而Test.c中包含#include"Heap.h"所以要在这里包含一下voidAdjustUp(HPDataType* a,int child);voidHeapInit(HP* php);voidHeapDestroy(HP* php);voidHeapPush(HP* php, HPDataType x);voidHeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);intHeapSize(HP* php);//Heap.cvoidHeapInit(HP* php){assert(php);
    php->a =NULL;
    php->size =0;
    php->capacity =0;}voidSwap(HPDataType* p1, HPDataType* p2){
    HPDataType tmp =*p1;*p1 =*p2;*p2 = tmp;}voidAdjustUp(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;}}}voidAdjustDown(int* 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[parent],&a[child]);
            parent = child;
            child = parent *2+1;}else{break;}}}//Test.cvoidHeapSort(int* a,int n){
    HP hp;HeapInit(&hp);for(int i =1;i<n; i++){//堆向上调整算法AdjustUp(a, i);//当i=0时，也就是孩子下标是0此时一个数据可以看作一个堆所以从1开始向上调整}int end = n -1;while(end >0){//小堆为例通过建堆第一个肯定是最小数Swap(&a[0],&a[end]);//调整选出次小数AdjustDown(a, end,0);//这里的end是n-1是最后一个数据的下标也是除了最后一个数据外前面数据的个数，所以可以传end过去
        end--;}}intmain(){//HPTest();int a[]={7,8,3,5,1,9,5,4};HeapSort(a,sizeof(a)/sizeof(a[0]));return0;}

💫1.1.2 流程图(以小堆为例)：升序：建大堆

最后得到的就是一个升序

💫1.1.3 流程图(以小堆为例)：降序：建小堆

最后得到的就是一个降序

🌏1.2 向下调整建堆(堆排序)：

💫1.2.1 完整代码：

//Heap.h#include<stdio.h>#include<assert.h>#include<stdlib.h>#include<stdbool.h>typedefint HPDataType;typedefstructHeap{
    HPDataType* a;int size;int capacity;}HP;voidAdjustDown(int* a,int n,int parent);voidAdjustUp(HPDataType* a,int child);voidHeapInit(HP* php);voidHeapDestroy(HP* php);voidHeapPush(HP* php, HPDataType x);voidHeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);intHeapSize(HP* php);//Heap.cvoidHeapInit(HP* php){assert(php);
    php->a =NULL;
    php->size =0;
    php->capacity =0;}voidSwap(HPDataType* p1, HPDataType* p2){
    HPDataType tmp =*p1;*p1 =*p2;*p2 = tmp;}voidAdjustUp(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;}}}voidAdjustDown(int* 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[parent],&a[child]);
            parent = child;
            child = parent *2+1;}else{break;}}}//Test.c#include"Heap.h"//直接建堆来调整---向下调整建堆voidHeapSort(int* a,int n){
    HP hp;HeapInit(&hp);for(int i =(n-1-1)/2; i >=0; i--){AdjustDown(a, n, i);}int end = n -1;while(end >0){Swap(&a[0],&a[end]);AdjustDown(a, end,0);
        end--;}}intmain(){//HPTest();int a[]={7,8,3,5,1,9,5,4};HeapSort(a,sizeof(a)/sizeof(a[0]));return0;}

💫1.2.2 流程图：

🌟二、两种建堆方式时间复杂度比较：

通过对两种建堆方式的比较更建议使用向下调整建堆但是向上调整建堆更容易理解看个人情况

🌏2.1 向上调整建堆：

🌏2.2 向下调整建堆：

🌟三、堆排序的时间复杂度：O(N*logN)

🌟四、呼应一下上章节的部分：利用堆使数据有序(不建议)

利用创建的堆数组排序:我们可以采用下面这种方法 — 先建堆(NlogN)太麻烦，然后来回拷贝数据(空间复杂度高)—具体代码可以看【数据结构】— 博主拍了拍你并向你扔了一“堆”二叉树(堆的概念+结构+代码实现)其中只有Test.c文件中做了以下修改其余没变

voidHeapSort(int* a,int n){
        HP hp;HeapInit(&hp);//建堆N*logNfor(int i =0;i<n; i++){HeapPush(&hp, a[i]);}//N*logNint i =0;while(!HeapEmpty(&hp)){int top =HeapTop(&hp);
            a[i++]= top;HeapPop(&hp);}for(int i =0; i < n; i++){printf("%d ", a[i]);}HeapDestroy(&hp);}intmain(){int a[]={7,8,3,5,1,9,5,4};HeapSort(a,sizeof(a)/sizeof(a[0]));return0;}

🌟五、TOP-K问题：

🌏5.1 TOP-K问题思路：

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

对于Top-K问题，能想到的最简单直接的方式就是排序

但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。
最佳的方式就是用堆来解决，基本思路如下：

🌏5.2 TOP-K问题代码：

在1000个数中找到前5个最大的数

除了Test.c作了以下改变Heap.h和Heap.c依据上面

//Test.c#define_CRT_SECURE_NO_WARNINGS1#include"Heap.h"#include<time.h>voidCreateNDate(){// 造数据int n =1000;srand(time(0));//产生随机数constchar* 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);}voidPrintTopK(int k){constchar* file ="data.txt";
    FILE* fout =fopen(file,"r");//以读的方式if(fout ==NULL){perror("fopen error");return;}//malloc空间int* kminheap =(int*)malloc(sizeof(int)* k);if(kminheap ==NULL){perror("malloc fail");return;}//读取前K个数据for(int i =0; i < k; i++){fscanf(fout,"%d",&kminheap[i]);}//建堆(建小堆)for(int i =(k -1-1)/2; i >=0; i--){AdjustDown(kminheap, k,i );}//比较覆盖int val =0;while(!feof(fout))//文件读取结束就跳出循环{fscanf(fout,"%d",&val);//从k+1数据开始读取和堆顶数据比较if(val > kminheap[0]){
            kminheap[0]= val;//覆盖AdjustDown(kminheap, k,0);}}for(int i =0; i < k; i++){printf("%d ",kminheap[i]);}printf("\n");}intmain(){CreateNDate();PrintTopK(5);return0;}

🌟六、文件操作：

可以看 C语言 — 文件操作(万字详解)

😽总结

😽Ending,今天的 堆排序+TOP-K问题 的内容就到此结束啦~，如果后续想了解更多，就请关注我吧，一键三连哦 ~