堆排序算法和Topk思想
目录
1>>导言
2>>堆排序
2.1>>通过堆结构实现堆排序
2.2>>堆思想实现排序
3>>Topk思想
4>>代码
5>>结语
1>>导言
今天重点内容就是带着大家实现堆排序和Topk，堆排序分为两种，一种是直接调用堆的数据结构来实现的，另一种就是通过堆的思想实现的，Topk就是在一个数组中寻找前k个最大/最小的数，通常利用在世界五百强企业、十大富豪等等。
2>>堆排序
2.1>>通过堆结构实现堆排序
1.首先给了一个数组，我们需要统计出它的大小。
2.创建一个堆结构变量hp，并且初始化它。注意：传的是地址
3.往这个堆中传递arr数组的每个数
4.循环判断，当堆不为空时，每次取根节点，然后删除根节点（删除操作还记得叭？就是讲最后结点和根结点互换，然后size--，就可以将最后一个结点删除，然后将新的根结点向下调整）
5.每次取出的头结点（根据大堆就是最大，小堆就是最小），所以最终就是一个降序/升序啦！
这边以大根堆为结果，宝子们可以去试试噢
2.2>>堆思想实现排序
1.要实现堆排序，首先得要是一个堆，那么第一个循环就要把堆建立，双亲结点向下调整思想，从最后一个结点的双亲结点开始（最后一个结点是n-1)它的双亲结点是-1然后除2，依次向下调整，这样就是一个堆。
2.将这个棵树的每一个子树都想象成一个堆，然后：
3.从最后一个结点开始，到0为止，每次交换它的最后一个结点和第0个结点，然后向下调整，这样就能够从大/从小排序
问题：要实现升序建（大堆/小堆）？要实现降序建（大堆/小堆）？
答案是：升序建大堆，降序建小堆，因为升序每次交换将最大的移到最后面了所以要大堆。
这是最终结果
3>>Topk思想
首先我们来造一个空间为100000的文件，通过之前章节学的随机数初始化文件每个数值
srand表示更改随机数初始值
创建一个file的文件，存放字符指针，叫data.txt
通过fopen打开文件file，w表示写入，若返回不为空则开始往变量fin写数据
最后关闭文件。
上面步骤稍微过一遍，现在开始实现topk，这才是重点：
void TopK()
{int k = 0;printf("请输入K：");scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");exit(1);}//找最大的前K个数，建小堆int* minHeap = (int*)malloc(sizeof(int) * k);if (minHeap == NULL){perror("malloc fail!");exit(2);}//读取文件中前K个数据建堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}// 建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {adjustdown(minHeap, i, k);}//要最大就建小堆，要最小就键大堆int x = 0;while (fscanf(fout, "%d", &x) != EOF) {if (x > minHeap[0]) {minHeap[0] = x;adjustdown(minHeap, 0, k);}}for (int i = 0; i < k; i++) {printf("%d ", minHeap[i]);}
}输入指定空间/堆大小k，然后读取文件每组数字，要找最大的前k个数，就要建小堆，就跟我们要最大值取最小值min一样的，若返回不为空，那么开始建堆，取前k个数据，建堆，跟建堆思想一样，从最后一个结点的父节点开始，依次向下调整，最后循环遍历文件的每一个数，如果读取到的数数大于我们的根结点，那么另根结点等于它，然后依次向下调整即可
这是文件中的数
4>>代码
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"void test()
{HP hp;hpinit(&hp);hppush(&hp, 1);hppush(&hp, 2);hppush(&hp, 4);hppush(&hp, 5);hppop(&hp);hppop(&hp);hppop(&hp);hpdestroy(&hp);
}
void test1() {int arr[] = { 17,20,10,13,19,15 };int n = sizeof(arr) / sizeof(arr[0]);HP hp;hpinit(&hp);int i = 0;for (i = 0; i < n; i++) {hppush(&hp, arr[i]);}i = 0;while (!hpempty(&hp)) {arr[i++] = hptop(&hp);hppop(&hp);}for (i = 0; i < n; i++) {printf("%d ", arr[i]);}
}
void HeapSort(int* arr, int n) {//自己实现堆排序for (int i =(n-1-1)/2; i >= 0; i--) {adjustdown(arr, i, n);}int end = n - 1;//最后一个结点开始，到0 为止while (end) {//大根堆swap(&arr[0], &arr[end]);adjustdown(arr, 0, end);//end一直--；end--;}//大根堆为升序
}
void CreateNDate()
{// 造数据int n = 100000;srand((unsigned int)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() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
void TopK()
{int k = 0;printf("请输入K：");scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");exit(1);}//找最大的前K个数，建小堆int* minHeap = (int*)malloc(sizeof(int) * k);if (minHeap == NULL){perror("malloc fail!");exit(2);}//读取文件中前K个数据建堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}// 建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {adjustdown(minHeap, i, k);}//要最大就建小堆，要最小就键大堆int x = 0;while (fscanf(fout, "%d", &x) != EOF) {if (x > minHeap[0]) {minHeap[0] = x;adjustdown(minHeap, 0, k);}}for (int i = 0; i < k; i++) {printf("%d ", minHeap[i]);}
}
int main()
{/*test();*///test1();//int arr[] = { 17,20,10,13,19,15 };//int n = sizeof(arr) / sizeof(arr[0]);//HeapSort(arr, n);////int i;//for (i = 0; i < n; i++) {// printf("%d ", arr[i]);//}//CreateNDate();TopK();return 0;
}#include"heap.h"void hpinit(HP* php) {assert(php);php->arr = NULL;php->size = php->capacity = 0;
}bool hpempty(HP* php) {assert(php);return php->size==0;
}
int hpsize(HP* php) {assert(php);return php->size;
}void adjustup(hpdatatype* arr, int child) {//向上调整，parent为（child-1）/2； leftchild为parent*2+1，rightchild为parent*2+2int parent = (child - 1) / 2;//为根结点即为0结束while (child > 0) {//小根堆<，从上往下每个子孙都比我大//大根堆>，从上往下每个子孙都比我小if (arr[child] > arr[parent]) {//两数交换swap(&arr[child], &arr[parent]);//孩子和双亲结点往上走child = parent;parent = (child - 1) / 2;}else {break;}}
}
void hppush(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->arr, newcapacity * sizeof(hpdatatype));if (tmp == NULL) {perror("realloc");exit(1);}php->arr = tmp;php->capacity = newcapacity;}//扩容结束//存放数据，每次存放就要比较，以小根堆为例子//0 1 2 3 size为4，新加入的数据下标为sizephp->arr[php->size] = x;//加入的不一定是与祖先比较大的数，因此需要向上调整adjustup(php->arr, php->size);//交换完毕size++php->size++;
}void adjustdown(hpdatatype* arr, int parent,int size) {//向下调整，leftchild为parent*2+1，rightchild为parent*2+2int child = parent * 2 + 1;//大于等于总结个数n即为size结束while (child<size) {//小根堆，从上往下每个子孙都比我大//大根堆，从上往下每个子孙都比我小//此时用小根堆//先要判断左孩子和右孩子哪个更小if (child + 1 < size && arr[child] > arr[child + 1]) {child++;}//两数交换//孩子和双亲结点往下走if (arr[child] < arr[parent]){swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}void hppop(HP* php) {assert(php);assert(!hpempty(php));//删除堆顶数据不能直接删除//否则会大乱套//思路：根屁股结点互换，然后让新的堆顶向下调整,size--//屁股为size-1；swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;adjustdown(php->arr,0,php->size);}
hpdatatype hptop(HP* php) {assert(php);return php->arr[0];
}
void swap(int* child, int* parent) {int tmp = *child;*child = *parent;*parent = tmp;
}
void hpdestroy(HP* php) {assert(php);assert(!hpempty(php));if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}5>>结语
这篇讲的算法思想——堆排序和topk，希望对宝子们有所帮助，有不懂的欢迎评论区指出，也欢迎大佬们指点小编的文章，谢谢大家观看，期待与你下篇再见~