目录
一.建堆的时间复杂度
向上调整算法
向下调整算法
二.堆排序
三.TOP-K问题.
一.建堆的时间复杂度
建堆有两种方式，一种是从堆顶开始向下建堆，另一种是从堆尾开始向上建堆，好像两种建堆方式除了向上调整和向下调整方式不同之外没什么区别，但我们仔细分析一下，其实这两种建堆方式的时间复杂度差别是很大的。
向上调整算法
首先,按照最坏时间复杂度分析,我们假设堆是完全二叉树中的满二叉树,并且假设每个结点都要移动最多次数（即从该节点的当前层数移动到第一层所需的次数）则:
可以知道，向上调整算法的时间复杂度是：O（N）=n*logn
向下调整算法
同样的按照最坏时间复杂度分析,我们假设堆是完全二叉树中的满二叉树,并且假设每个结点都要移动最多次数（即从该节点的当前层数移动到第一层所需的次数）则:
可以知道，向下调整算法的是时间复杂度是：O(N) = n
二.堆排序
堆排序就是利用堆(假设利用大堆)进行排序(假设为升序)的算法.
它的基本思想是:首先将所有的元素集合起来，创建一个堆结构，考虑到向下调整算法的时间复杂度较低，所以用向下调整算法建堆。建堆完成以后，就是一个大堆，堆顶数据是堆中数据的最大值，对堆顶元素进行出堆操作。由于出堆会改变当前堆的性质，所以需要向下调整。再对堆顶出堆，再重新调整......如此返回操作直到只剩一个节点，这样就得到一个有序序列了。
借助图像理解：
逻辑结构：
物理结构：
需要注意的是：由于需要将堆顶数据与堆尾位置的数据交换，使得堆顶元素得以保存下来，所以如果排升序序列，序列的最后一个数据就是第一次出堆时堆顶数据，是堆的最大值，所以排升序序列要建大堆。排降序序列建小堆。
且向下调整建堆参数是父节点，第一个父节点的位置是（child - 1）/2，然后每次调整完毕直接将父节点的下标-1，直到父节点的下标为0（为0也要参与向下调整）。
向上调整建堆的话，假设是一个数据一个数据参与堆结构的创建，一开始是一个数据，该数据就是堆顶，然后是第二个数据，这个数据要与堆顶比较（向上调整），如此遍历数据，直到数据全部都在堆结构中。
代码如下：
//交换函数 void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } //向下调整建堆 void AdjustDown(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[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } //堆排序(升序 void HeapSort(int* a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; i--)//先向下调整建堆 { AdjustDown(a, n, i); } int end = n - 1; while (end > 0) { Swap(&a[end], &a[0]);//将堆顶元素和待排区间的最后一个元素交换 AdjustDown(a, end, 0); end--; } } int main1() { //test01(); //test02(); int arr[6] = {19,15,20,17,13,10}; printf("排序之前："); arrPrint(arr, 6); //堆排序 HeapSort(arr, 6); printf("排序之后："); arrPrint(arr, 6); return 0; }三.TOP-K问题.
求数据集合中前k个最大/最小的元素，一般情况下数据量都比较大。
这时的最佳的方案就是用堆来解决，思路如下:
1.先用数据元素中前K个元素来建堆
求前k个最大的元素,则建小堆
求前k个最小的元素,则建大堆
2.遍历剩余的N-K个元素来比较,遇到符合条件的(如求前k个最大的元素,新元素比堆顶要大)则用其替换堆顶,然后再向下调整,构建为新的大堆/小堆.3.当遍历完剩下N-K个元素时,堆中剩余的k个元素就是所求的前Top-k个元素
为什么求前 K 大，要用小顶堆
口诀：求大用小堆，求小用大堆，很多人这里会搞反，拆开讲明白。
假设：要找数组里最大的 3 个元素，K=3，候选：
9，8，5小顶堆特点
小顶堆，堆顶 =堆里面所有元素的最小值。如果堆固定只存K=3 个数字，那堆顶就是「当前这 3 个里面最弱的那个」。
完整逻辑推演
- 堆里面只允许放 K 个元素，代表目前筛选出来的 Top‑K。
K=3，堆里存
5,9,8，小顶堆堆顶是5（三个里面最小）
- 新来一个数字 x，拿 x 和堆顶对比：
- 如果
x > 堆顶(5)：x 比我们 Top3 里最弱的还要大，有资格进 Top3。把堆顶（5，最弱的候选）删掉，把 x 放进去。- 如果
x <= 堆顶(5)：x 连当前 Top‑K 里最弱的都比不过，直接抛弃。堆顶相当于 “门槛”，比门槛大就替换门槛。
❓那为什么不能用大顶堆？
如果用大顶堆存 K 个元素：大顶堆堆顶是堆里的最大值。堆里面 K 个数字，堆顶是最大的，你根本不知道 K 个里面谁最小！新来一个数字，你没法快速判断这个数够不够资格进 TopK。
大顶堆只能知道谁最大，不知道 K 个里面的底线（最小值），做不到筛选。
当然你也可以建一个 n 大小的大顶堆，循环 pop K 次拿最大值。但复杂度是 O(nlogn)。而小顶堆只维护 K 个节点，每次操作 logK，总复杂度 O(nlogK)。当 n 很大（百万、海量数据），K 远小于 n 的时候，速度差距巨大。
举实例
数组：
[2,7,3,9,1,8,4]，找最大 3 个。K=3，小顶堆容量固定 3。
- 前 3 个入堆：
2,7,3，小顶堆堆顶 =2（门槛是 2）- 下一个 x=9：9>2 → 弹出 2，压入 9；堆：
3,7,9，门槛变成3- x=1：1<3，直接跳过
- x=8：8>3 → 弹出 3，压入 8；堆：
7,9,8，门槛变成7- x=4：4<7，直接跳过
遍历结束，堆内
7,9,8，就是最大 3 个元素，堆顶7就是第 3 大元素。反向：求前 K 小，建大顶堆
找最小 K 个，堆内存 K 个候选，大顶堆堆顶 = 堆内最大值（门槛）新来数字比堆顶更小，就替换堆顶。
考试一句话答案（写卷子）
求前 K 个最大元素，构建大小为 K 的小顶堆。堆顶代表当前 K 个候选元素中的最小值，作为筛选门槛；若新元素大于堆顶，则说明该元素属于前 K 大，替换堆顶。堆的大小始终维持 K，时间复杂度O(nlogK)。
记忆技巧
要保留 K 个最好的，堆顶放这 K 个里面最差的，用来当门槛。
- K 个最大的，K 里面最差的就是最小 →小顶堆
- K 个最小的，K 里面最差的就是最大 →大顶堆
代码如下：
//topk void CreateNDate() { // 造数据 int n = 100000; 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() + 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 fail!"); exit(1); } //找最大的前K个数据，建小堆 int* minHeap = (int*)malloc(sizeof(int) * k); if (minHeap == NULL) { perror("malloc fail!"); exit(2); } for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minHeap[i]); } //minHeap -- 向下调整建堆 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) { //X minHeap-top if (x < minHeap[0]) { minHeap[0] = x; AdjustDown(minHeap, 0, k); } } for (int i = 0; i < k; i++) { printf("%d ", minHeap[i]); } fclose(fout); } int main() { //CreateNDate(); TopK(); return 0; }
