目录一.建堆的时间复杂度向上调整算法向下调整算法二.堆排序三.TOP-K问题.一.建堆的时间复杂度建堆有两种方式一种是从堆顶开始向下建堆另一种是从堆尾开始向上建堆好像两种建堆方式除了向上调整和向下调整方式不同之外没什么区别但我们仔细分析一下其实这两种建堆方式的时间复杂度差别是很大的。向上调整算法首先,按照最坏时间复杂度分析,我们假设堆是完全二叉树中的满二叉树,并且假设每个结点都要移动最多次数即从该节点的当前层数移动到第一层所需的次数则:可以知道向上调整算法的时间复杂度是ONn*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 个元素K3候选985小顶堆特点小顶堆堆顶 堆里面所有元素的最小值。如果堆固定只存K3 个数字那堆顶就是「当前这 3 个里面最弱的那个」。完整逻辑推演堆里面只允许放 K 个元素代表目前筛选出来的 Top‑K。K3堆里存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 个。K3小顶堆容量固定 3。前 3 个入堆2,7,3小顶堆堆顶 2门槛是 2下一个 x992 → 弹出 2压入 9堆3,7,9门槛变成3x113直接跳过x883 → 弹出 3压入 8堆7,9,8门槛变成7x447直接跳过遍历结束堆内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; }