Java - TopK问题 + 堆排序

开篇

TOPK 问题,就是从一个数组中,找出最大的前 K 位
例如: arr[] = {4,2,1,7,5,3,9,0} 从这个数组中找出最大的 3 个

全局排序 -- 简单粗暴

通常看到这种问题,最简单的方法就是排序了,将这n个数倒序排序,直接取排在前面的k个,就是想要的。时间复杂度 : O(n * lg(n))
分析：在问题里面,最开始本来想要的是最大的前3个,其实这3个之后的我们大可以不必去管它的顺序的,但是直接排序在这个里面对全局进行了一次排序,就导致做了一些额外的操作,时间复杂度也就提高了。过程如下, sort 是对整个数组进行排序

全局排序.png

局部排序 -- 不完全冒泡排序

不再全局排序,只对最大的k个进行排序,例如冒泡法,每次冒一个泡就得到了一个最大值,冒k个泡就得到了TopK。时间复杂度 O(n*k)。过程如下图所示.分析一下,这种方法相对于第一种方法可以说是优化了不少的,但是还是有一个弊端,每找到1个最大的数，这个数都需要和全部的数进行一次比较才能知道它是较大的，然后程序还要维护一份这前 K 个数的顺序

冒泡排序

继续优化-- 堆排序

在局部排序中,我们对这前 K 个数还维护了一份顺序,这样还是会比较耗时的,在TOPK的问题里我们只是想得到最大的5个数。有一种新的解决办法,就是堆排序
堆排序的思路：只找到 TopK,不排序 TopK 先用前 K 个元素生成一个小顶堆(简单理解就是二叉树),这个小顶堆后面就会用来存储当前最大的 K 个元素，过程如下图所示:
分析:这种方法时间复杂度 O(nlogk) , 存在运气的成分，一次遍历就能够把前 k 个需要的数字找出来,但是也有缺点,缺点是每次都需要维护小顶堆的堆顶为这个堆的最小值。此外算导里还有一种 O(N) 的随机选择的方法，思路是和快排的分治思想结合到一起的，有兴趣可以去算导书里了解下。

堆排序