目录
一、什么是Top K问题
二、Top K的实际应用场景
三、Top K的代码实现及其效率对比
1.用堆来实现Top K
2.用快排来实现Top K
3.用堆或用快排来实现 TopK 的效率对比
正文
一、什么是Top K问题？
给一个无序的数组，长度为N， 请输出最小 （或最大）的K个数。
二、Top K的实际应用场景
排行榜：用户数量有几百万， 但是只需要前100名的用户成绩。 要显示出来， 且这个排行榜是实时变化的。
三、Top K的代码实现
需求：给一个无序的数组，长度为N， 请输出最大的5个数。
1. 用堆来实现Top K——PriorityQueue（小顶堆）
（1）步骤梳理：
①创建一个结点个数为 k 的小顶堆；
②当数据量 < k 时，将数据直接放到这个小顶堆中，此时堆的顶结点是最小值；
③当数据量 >= k时，每产生一个新数据都与堆的顶结点进行比较:
如果新数据 > 顶结点数据，则将顶结点删除，将新数据放到堆中，此时堆会进行排序，且维护了堆的总结点数为k;
如果新数据＜顶结点数据，则不动。
（2）中心思想：使堆的总结点数维持在 k 个。
（3）代码实现：
@Test
public void getTopKByHeapInsertTopKElement() {
int arrayLength = 10000000 + 10;
int topK = 5; // 准备一个长度为arrayLength的无序数组：
int[] array = A03TopKByQuickSortAndNewArray.getDisorderlyArray(arrayLength); // 准备一个总结点数为topK的小顶堆：
PriorityQueue<Integer> heap = new PriorityQueue<>(topK); long start = System.currentTimeMillis(); // 始终维持一个总结点个数为k的堆：
insertButmaintainTheHeapAtTopK(heap, array, topK); //获得最大topK：
printHeap(heap); long end = System.currentTimeMillis();
System.out.println("获得最大top5总耗时： " + (end - start));
} /**
* 用小顶堆来获取topK：当数据量超过topK后，新产生的数据直接和heap的顶结点进行比较。
*/
private static void insertButmaintainTheHeapAtTopK(PriorityQueue<Integer> heap, int[] array, int topK) {
for (int i = 0; i < array.length; i++) {
if (i < topK) {
heap.add(array[i]);
} else {// 怎么维持堆的总结点个数，下面的代码是关键：
if (null != heap.peek() && array[i] > heap.peek()) {
heap.poll();
heap.add(array[i]);
}
}
}
} /**
* 获取最大TopK
* @param heap
*/
static void printHeap(PriorityQueue<Integer> heap) {
Iterator<Integer> iterator = heap.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
2. 用快排来实现Top K
（1）步骤梳理：
①通过快排，先将无序数组array进行排序；
②取出最小Top 5，并放到topArray中；【关键】
③超过arrayLength个数据后，又产生了insertNumber个新数据：直接和topArray数组比较，要放也是放到topArray中了；【关键】
（2）时间复杂度：
①排序的时间复杂度：O(N*logN)；
②取出top k的时间复杂度：O(1)，就是遍历数组。
（3）代码实现：
@Test
public void testGetTopKByQuickSortToNewArray() {
int topK = 5;
int arrayLength = 10000000; //准备一个无序数组
int[] array = getDisorderlyArray(arrayLength); long start = System.currentTimeMillis(); //1.通过快排，先将无序数组array进行排序
quickSort(array, 0, array.length-1); //2.取出最小Top 5，并放到topArray中：
int[] topKArray = insertToTopArrayFromDisorderlyArray(array, topK); //3.超过arrayLength个数据后，又产生了insertNumber个新数据：直接和topArray[topKArray.length-1]比较，要放也是放到topArray中了
insertToTopKArray(topKArray, 10, 100, topKArray.length-1);//生成10个100以内的随机数作为新数据，和topKArray[topKArray.length-1] long end = System.currentTimeMillis();
System.out.println("获得最大top5总耗时： " + (end - start));
} /**
* 产生新的数据后，再和topKArray数组进行比较，看新数据时候需要插入到topKArray中，若需要插入，则堆topKArray进行重新快排。
*
* @param topKArray topK数组
* @param insertNumber 新产生的数据的个数
* @param randomIntRange 在什么范围内产生新数据，如生成10以内的随机数。
* @param topK 在topKArray中，确定要替换的元素的下标。获得最小topK，则topK是从小到大排序的topKArray的最后一个元素。
*/
private static void insertToTopKArray(int[] topKArray, int insertNumber, int randomIntRange, int topK) {
Random random = new Random();
int randomInt;
for(int i = 0; i < insertNumber; i++) {
randomInt = random.nextInt(100);
if(randomInt < topKArray[topK]) {//新数据如果小于topArray[topK]，则直接用该数去替换topArray，然后再将topArray进行重新排序。
topKArray[topK] = randomInt;
quickSort(topKArray, 0, topKArray.length-1);
}
}
} /**
* 从有序数组中取出需要的TopK，放到TopK数组中。
*
* @param sourceArray 有序数组
* @param topK 需要获取到Top K
* @return TopK数组
*/
private static int[] insertToTopArrayFromDisorderlyArray(int[] sourceArray, int topK) {
int[] topArray = new int[topK];
for(int i = 0; i < 5; i++) {
topArray[i] = sourceArray[i];
}
return topArray;
} /**
* 快排
* @param target
* @param left
* @param right
*/
static void quickSort(int[] target, int left, int right) {
if (left >= right) {
return;
}
int pivot = target[left];// 基准点
int temp;
int i = left;
int j = right;
while (i < j) {
while (target[j] >= pivot && i < j) {
j--;
}
while (target[i] <= pivot && i < j) {
i++;
}
if (i < j) {
temp = target[i];
target[i] = target[j];
target[j] = temp;
}
}
// left和right相遇了：
// ①将相遇点的元素和pivot做交换：
target[left] = target[j];
target[j] = pivot;
// ②基准点两边的元素的分别再做排序：
quickSort(target, left, j - 1);
quickSort(target, j + 1, right);
} /**
* 准备一个无序数组
*
* @param arrayLength
* @return int[]
*/
static int[] getDisorderlyArray(int arrayLength) {
int[] disorderlyArray = new int[arrayLength];
Random random = new Random();
for (int i = 0; i < arrayLength; i++) {
disorderlyArray[i] = random.nextInt(arrayLength);
}
return disorderlyArray;
} /**
* 遍历数组
*/
static void showArray(int[] target) {
for (Integer element : target) {
System.out.println(element);
}
}
3. 用堆来实现TopK 和 用快排来实现TopK 的效率对比：
“小顶堆” | “快排”
数据量为100万+10时： 11毫秒 | 124毫秒
数据量为1000万+10时： 28毫秒 | 1438毫秒