本文主要是介绍堆排序-升序和降序_TopK-N个数找找最大的前K个，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤:
1.建堆
升序:建大堆
降序:建小堆
2.利用堆删除思想来进行排序
方法一：把数据拷贝进堆、把堆拷贝进数据
//弊端，1.需要先有一个堆 2.时间复杂度+拷贝数据
void HeapSort(int* a, int n)
{HP hp;HeapInit(&hp);//建堆--向上调整建堆for (int i = 0; i < n; i++) //N*logN{HeapPush(&hp,a[i]); //把数据拷贝进堆}int i = 0;while (!HeapEmpty(&hp)) //N*logN{ int top = HeapTop(&hp);a[i++] = top; //把堆拷贝进数据HeapPop(&hp);}HeapDestory(&hp);
}int main()
{int a[] = { 1,5,6,7,8,9,3,4,6 };HeapSort(a, sizeof(a) / sizeof(a[0]));return 0;
}
改进思路：
升序–
建小堆？ 存在可能把兄弟结点互换的情况，堆的关系可能会全乱，只能重新建堆。
建大堆，将元素第0个和最后一个互换，则最后一个就是最小元素。然后将该元素隔离开。
然后依次操作。
反之，降序–建小堆。
方法二：建堆，调整位置，再整理堆
void HeapSort(int* a, int n)
{//升序 建大堆--//降序 建小堆//建堆--向上调整建堆/*for (int i = 0; i < n; i++) {AdjustUp(a,i); //从根结点的孩子开始一一向上调整}*///建堆--向下调整建堆--O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){ //int i = (n - 1 - 1) / 2 从倒数第一个非叶子结点倒着走，AdjustDown(a, n, i); //建小堆，叶子结点不需要处理}//效率上存在差异//升序？降序？建堆时候注意建大堆还是小堆//调整顺序int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);//再调整，选出次小的数AdjustDown(a,end,0);--end; //最后一个数不能看作堆里的}
}int main()
{int a[] = { 1,5,6,7,8,9,3,4,6 };HeapSort(a, sizeof(a) / sizeof(a[0]));return 0;
}
调试观察：
第一次和第二次的调试结果
程序运行结束的结果为：
符合我们的预想，降序建立小堆
二、TopK-N个数找找最大的前K个
改进思路:
1.将前K个数拷贝进新创建的空中中，建小堆；
2.后N-K个数与堆项元素一一比较，比堆项元素大，就调换他们的位置；
3.前K个数保持小堆，需要向下调整调换过位置；
4.最后的小堆的值就是前K个数。
#define _CRT_SECURE_NO_WARNINGS#include "HeapTopK.h"void CreateDate()//创建数据
{int n = 1000000;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() % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void TopK(int k) //K=5
{//打开文件const char* file = "data.txt";//const char* file = "data1.txt"; //修改data1.txt中数为最大数，然后检验查看FILE* fount = fopen(file, "r");if (fount == NULL){perror("fount fail");return;}//开辟k个空间，读出前k个数据放在一个数组中int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("kminheap fail");return;}for (int i = 0; i < k; i++){fscanf(fount, "%d", &kminheap[i]);}//建小堆for (int i = (k - 1 - 1) / 2; i >= 0; --i){AdjustDown(kminheap, k, i);}//将fout中的元素(指针已经到了k+1个）val与kminheap中的堆顶元素（kminheap中最小的值）对比int val = 0;while (!feof(fount)){fscanf(fount, "%d", &val);//从fount中读取的值赋值给valif (val > kminheap[0]){kminheap[0] = val;AdjustDown(kminheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}}int main()
{CreateDate();TopK(5); //K=5return 0;
}
HeapTopK.c,HeapTopK.h的代码不赘述。
其中需要注意 srand，time 需要包含的头文件分别为<stdlib.h>,<time.h>.
这篇关于堆排序-升序和降序_TopK-N个数找找最大的前K个的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
