邢台做网站推广费用《网站开发与应用》试题
1.堆排序
想法⼀：
基于已有数组建堆、取堆顶元素完成排序。也就是利用写好的堆数据结构（之前的文章有讲解），去实现排序。
void HeapSort(int* a, int n){HP hp;for(int i = 0; i < n; i++){HPPush(&hp,a[i]);}int i = 0;while (!HPEmpty(&hp)){a[i++] = HPTop(&hp);HPPop(&hp);}HPDestroy(&hp);先依次入堆，然后再将堆顶，数据依次取出，为大堆即是降序，小堆为升序。实际上这种方法使用起来是很不方便的，必须要有堆的数据结构，而且时间复杂度为O（n）。
想法⼆：
数组建堆，⾸尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次⼤的数据。
void HeapSort(int* arr, int n)
{//根据给定的arr来进行建堆//child:n-1 parent:(n-1-1)/2向下调整算法建堆//for (int i = (n - 1 - 1) / 2; i >= 0; i--)//O(n)//{// AdjustDown(arr, i, n);//O(logn)//}//向上调整建堆for (int i = 0; i < n; i++){AdjustUp(arr, i);}//堆排序//排升序---建大堆//排降序---建小堆int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}}这里利用的是堆的思想，而不是直接用堆来排序，首先要建堆，将传进来的数组入堆，这里以建小堆为例，利用向下调整的方法，将一个个依次调整直到，直到根节点；
这里完成了建堆，那后面接下来，排序怎么办，其实利用思想将堆顶元素，与最后一个元素交换，再将元素个数减一，将剩余的堆进行调整，依次交换直到到堆顶。最后发现建的小堆，其实是降序排列，反之降序是建小堆。
这样就排序完成。
注意：这里考虑一个问题，向上调整可以建堆，向下调整也可以建堆，那个时间复杂度更低。
1.2向上调整算法和向下调整算法比较：
向上调整算法：
往下结点个数逐渐增多，向下调整次数增多；
可以推出向上调整建堆时间的复杂度：O(n*logn)；
向下调整算法：
可以推出向下调整建堆时间的复杂度：O（n）；
比较发现向下调整算法更优。
2.TOP-K问题
TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。 ⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决，基本思路如下：
第一步：⽤数据集合中前K个元素来建堆
（这和前面堆排序有一些相似）
前k个最⼤的元素，则建⼩堆；
前k个最小的元素，则建⼤堆；
第二步：⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素
将剩余N-K个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素
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);}//遍历剩下的n-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]);}fclose(fout);
}这里一些文件操作函数，可以看看小编前面的文章有讲解。