堆排序和topk问题

系列文章目录

前言

常见的基本排序算法有冒泡、选择、插入，但效率太低。
堆排序和快速排序算法则是相对高效的算法。这篇主要先介绍堆排序

一、堆排序定义

堆排序就是借助（大/小）堆的特性，实现的快速排序

二、时间复杂度

时间复杂度：N * log2
本质就是建堆后，借助堆来调整N个数的位置，每次调整时间为堆高度log2

三、实现思路

（以小堆为例）

1. 先将数据建小堆，此时堆顶是最小值。
2. 将堆顶元素与数组末尾的元素交换，此时最小值被放到数组末尾。
3. 将堆的有效长度-1，末尾元素视为已排序，不参与后续调整。
4. 对堆顶的元素进行向下调整，使其重新满足小堆的特性
5. 重复上述过程，直到堆的有效长度为1

//实现堆排序————时间复杂度：N * logN (一次向下调整是N, 执行N次)voidHeapSort(int*a,intn){//1、建堆for(inti=(n-1-1)/2;i>=0;i--)//需要从最后一个节点的父亲节点,开始向下调整{AdjustDown(a,n,i);}//2、将排序好的最小值，排出堆排序的范围intend=n-1;//3、再一直对根节点实现向下调整while(end>0){swap(&a[0],&a[end]);//再次选择最小的值AdjustDown(a,end,0);end--;}}

至此，实现了数组的降序排列

a.注意（升/降）

排升序，建大堆
排降序，建小堆

因为每次堆顶会和数组末尾的元素交换

四、topk问题

N个数中找出最大或最小的前K个数？

最优方案：建立一个K的数的堆。
如果想找K个最大数就建小堆，想找K个最小数就建大堆
（以小堆为例）

遍历N-K个数，凡是比堆顶大的数就替换堆顶数据，进堆向下调整。
（因为堆顶的数总是较小的）最后剩下的k个数就是前K个最大的数。

前K个最小的数同理可得。