上次介绍了堆排序，这次介绍堆排序常见应用场景的TopK问题。利用堆求TopK问题TopK问题是堆排序的典型应用场景。题目是这样的：假设我们要在大量数据中，比如100亿整数数据中，找出K个值最大的元素，K小于10000，你会怎么做呢？目标是力扣第215题：“数组中第K大的元素”。具体链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/在未排序的数组中寻找第k大的元素。请注意，您正在寻找排序数组的第k个最大元素，而不是第k个不同的元素。示例1：输入：[3,2,1,5,6,4]和k=2输出：5示例2：输入：[3,2,3,1,2,4,5,5,6]和k=4Output:4经典的TopK问题还包括：最大（小）K个数，前K个高频元素，第K大（小）元素。这个TopK问题本质上是一个排序问题，排序算法一共有十种，还有很多排序算法没有介绍。至于为什么TopK问题的最佳答案是堆排序？事实上，考虑到空间和时间的复杂性，虽然快速排序是最好的排序算法，但是它把100亿个元素从大到小排序，然后输出前K个元素值。但是不管我们是快排序算法还是堆排序算法，在排序的时候，都需要把所有的元素读入内存。也就是说，100亿个整??数元素需要占用大约40GB的内存空间，这听起来不像是普通民用电脑能做到的，（一般民用电脑内存都比这个小，比如我写文章用的电脑内存是32GB）。众所周知，快速排序和堆排序的时间复杂度是可以达到的，但是对于快速排序来说，数据是顺序访问的。对于堆排序，通过跳过访问数据。例如在堆排序中，最重要的操作就是数据的堆放。因此，快速排序的时间复杂度优于堆排序。但是快速排序是一个新的数组，空间复杂度比堆排序要低很多。对于海量数据，应该首选堆排序。如果使用heapq内置模块，查找数组中第K个最大的元素只是一行代码。封装了heapq中的nlargest接口，返回的数组是需要切片取值的数组。importheapqclassSolution:deffindKthLargest(self,nums:List[int],k:int)->int:returnheapq.nlargest(k,nums)[-1]当然一般是手写堆排序，找第K大的array为元素创建一个最小堆，找到数组中第K小的元素构建一个最大堆。思路是：“取nums的前K个元素构建一个大小为K的最小堆，然后维护一个容量为k的小顶堆。堆中的堆中的k个节点代表当前最大的k个元素，而堆顶显然是k个元素中的最小值。”因此，只要遍历整个数组，当二叉堆的大小等于K时，当遇到大于堆顶值的元素时，弹出堆顶，将元素弹出被推入，最大的K个元素被持续维护。遍历后，堆顶元素为第K大元素。时间复杂度。classSolution:deffindKthLargest(self,nums:List[int],k:int)->int:heapsize=len(nums)defmaxheap(a,i,length):l=2*i+1r=2*i+2large=iifl
