Top K问题在数据分析中非常普遍的一个问题（在面试中也经常被问到），比如：

从20亿个数字的文本中，找出最大的前100个。

解决Top K问题有两种思路，

最直观：小顶堆（大顶堆 -> 最小100个数）； 较高效：Quick Select算法。 LeetCode上有一个问题215. Kth Largest Element in an Array，类似于Top K问题。

1. 堆

小顶堆（min-heap）有个重要的性质——每个结点的值均不大于其左右孩子结点的值，则堆顶元素即为整个堆的最小值。JDK中PriorityQueue实现了数据结构堆，通过指定comparator字段来表示小顶堆或大顶堆，默认为null，表示自然序（natural ordering）。

小顶堆解决Top K问题的思路：小顶堆维护当前扫描到的最大100个数，其后每一次的扫描到的元素，若大于堆顶，则入堆，然后删除堆顶；依此往复，直至扫描完所有元素。Java实现第K大整数代码如下：

public int findKthLargest(int[] nums, int k) {  PriorityQueue
    
      minQueue = new PriorityQueue<>(k);  for (int num : nums) {    if (minQueue.size() < k || num > minQueue.peek())      minQueue.offer(num);    if (minQueue.size() > k)      minQueue.poll();  }  return minQueue.peek();}
    

2. Quick Select

Quick Select [1]脱胎于快排（Quick Sort），两个算法的作者都是Hoare，并且思想也非常接近：选取一个基准元素pivot，将数组切分（partition）为两个子数组，比pivot大的扔左子数组，比pivot小的扔右子数组，然后递推地切分子数组。Quick Select不同于Quick Sort的是其没有对每个子数组做切分，而是对目标子数组做切分。其次，Quick Select与Quick Sort一样，是一个不稳定的算法；pivot选取直接影响了算法的好坏，worst case下的时间复杂度达到了O(n2)。下面给出Quick Sort的Java实现：

public void quickSort(int arr[], int left, int right) {  if (left >= right) return;  int index = partition(arr, left, right);  quickSort(arr, left, index - 1);  quickSort(arr, index + 1, right);}// partition subarray a[left..right] so that a[left..j-1] >= a[j] >= a[j+1..right]// and return index jprivate int partition(int arr[], int left, int right) {  int i = left, j = right + 1, pivot = arr[left];  while (true) {    while (i < right && arr[++i] > pivot)      if (i == right) break;    while (j > left && arr[--j] < pivot)      if (j == left) break;    if (i >= j) break;    swap(arr, i, j);  }  swap(arr, left, j);  // swap pivot and a[j]  return j;}private void swap(int[] arr, int i, int j) {  int tmp = arr[i];  arr[i] = arr[j];  arr[j] = tmp;}

Quick Select的目标是找出第k大元素，所以

若切分后的左子数组的长度 > k，则第k大元素必出现在左子数组中； 若切分后的左子数组的长度 = k-1，则第k大元素为pivot； 若上述两个条件均不满足，则第k大元素必出现在右子数组中。 Quick Select的Java实现如下：

public int findKthLargest(int[] nums, int k) {  return quickSelect(nums, k, 0, nums.length - 1);}// quick select to find the kth-largest elementpublic int quickSelect(int[] arr, int k, int left, int right) {  if (left == right) return arr[right];  int index = partition(arr, left, right);  if (index - left + 1 > k)    return quickSelect(arr, k, left, index - 1);  else if (index - left + 1 == k)    return arr[index];  else    return quickSelect(arr, k - index + left - 1, index + 1, right);}

上面给出的代码都是求解第k大元素；若想要得到Top K元素，仅需要将代码做稍微的修改：比如，扫描完成后的小顶堆对应于Top K，Quick Select算法用中间变量保存Top K元素。

3. 参考资料

[1] Hoare, Charles Anthony Richard. "Algorithm 65: find." Communications of the ACM 4.7 (1961): 321-322. [2] James Aspnes, QuickSelect.