经典TopK的各种解法算法

问题描述：从arr[1]到arr[n]这n个数中，找出其中最大的k个数。

问题介绍

遇到在大规模数据处理中总会遇到“在海量数据中找出出现频率最高的前K个数据”之类的问题，这类问题被统称为TopK问题。优化解决TopK问题有助于我们在设计搜索引擎事实现热门关键词的排列，以及统计下载量等。
有一个1GB大小的文件，里面的每一行是一个词，词的大小不超过16个字节，内存限制大小是1MB。返回频数最高的100个词。
提取某日访问网站次数最多的那个IP。
搜索的输入信息是一个字符串，统计300万条输入信息中最热门的前10条，每次输入的一个字符串为不超过255B，内存使用只有1GB。
…

1. 排序最容易想到的方法当然是直接排序，将n个数排序之后，取出最大的前k个，即为所得。最快的排序算法的时间复杂度一般为O(NlogN)，如快速排序。伪代码如下：

sorted(arr, 1, n); return arr[1, k];

但是，同样存在以下问题：

快速排序的平均复杂度虽然为O(NlogN)，但是最坏的情况下却为O(2N)；
排序将所有元素都排列了，在数据量十分巨大的情况下，十分消耗内存，并且没有必要。因为我们只需要前k个数据。

所以，这给我们指了一条优化思路：我们能不能只对部分数据进行排序就找出我们需要的数据呢？ 2. 局部排序我们借鉴快速排序的思想。
先简单介绍一下快速排序：快速排序基本思想是随机选取一个数作为关键字，经过一趟排序，将整段序列分为两个部分，其中一部分的值都小于关键字，另一部分都大于关键字。然后继续对这两部分继续进行排序，从而使整个序列达到有序。
快排代码如下（C语言）：

void QuickSort(int* arr, int left, int right){ int mid = 0; if(left >= right){ return; } mid = Partition(arr, left, right); QuickSort(arr, left, mid - 1); QuickSort(arr, mid + 1, right); }int Partition(int* arr, int left, int right){ int key; int start = left; key = arr[left]; while(left < right){ while(left < right && arr[right] >= key) { right--; } while(left < right && arr[left] <= key) { left++; }Swap(&arr[left], &arr[right]); } Swap(&arr[left], &arr[start]); return left; }

我们借鉴快排的思想，在数组中随便找一个元素key，把数组分为arr_a, arr_b两部分，其中a组中的元素大于等于key，b组的元素小于k。那么：

如果a组中的元素个数大于等于k，那么我们只需要对a组进行排序并且查找最大的k个数；
如果a组中的元素个数小于k，而且长度为length，那么我们只需要在b组中查找接下来的k-length个数字。
算法实现如下（C语言）：

int findTopK(int* arr, int left, int right, int k){ int index = -1; if(left < right){ int pos = Partition(array, left, right); int len = pos - left + 1; if(len == k){ index = pos; } else if(len < k){//a中元素个数小于K，到b中查找k-len个数字 index = findTopK(array, pos + 1, right, k - len); } else{//a组中的元素个数大于等于k index = findTopK(array, left, pos - 1, k); } } return index; }

那么可不可以不排序也能找出前K个数呢？
3. 堆我们考虑用容量为K的小顶堆堆来存储最大的K个数。
先用前k个元素生成一个小顶堆，这个小顶堆用于存储，当前最大的k个元素。接着，从第k+1个元素开始扫描，和堆顶（堆中最小的元素）比较，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。直到，扫描完所有n-k个元素，最终堆中的k个元素即为所求。
这种方法当数据量比较大的时候，比较方便。因为对所有的数据只会遍历一次。
Java实现如下：

public class MinHeap { // 堆的存储结构为数组 private int[] data; // 将一个数组传入构造方法，并转换成一个小顶堆 public MinHeap(int[] data) { this.data = https://www.it610.com/article/data; buildHeap(); }// 将数组转换成最小堆 private void buildHeap() { // 完全二叉树只有数组下标小于或等于 (data.length) / 2 - 1 的元素有孩子结点，遍历这些结点。 for (int i = (data.length) / 2 - 1; i>= 0; i--) { // 对有孩子结点的元素heapify heapify(i); } }private void heapify(int i) { // 获取左右结点的数组下标 int l = left(i); int r = right(i); // 这是一个临时变量，表示跟结点、左结点、右结点中最小的值的结点的下标 int smallest = i; // 存在左结点，且左结点的值小于根结点的值 if (l < data.length && data[l] < data[i]) smallest = l; // 存在右结点，且右结点的值小于以上比较的较小值 if (r < data.length && data[r] < data[smallest]) smallest = r; // 左右结点的值都大于根节点，直接return，不做任何操作 if (i == smallest) return; // 交换根节点和左右结点中最小的那个值，把根节点的值替换下去 swap(i, smallest); // 由于替换后左右子树会被影响，所以要对受影响的子树再进行heapify heapify(smallest); }// 获取右结点的数组下标 private int right(int i) { return (i + 1) << 1; }// 获取左结点的数组下标 private int left(int i) { return ((i + 1) << 1) - 1; }// 交换元素位置 private void swap(int i, int j) { int tmp = data[i]; data[i] = data[j]; data[j] = tmp; }// 获取对中的最小的元素，根元素 public int getRoot() { return data[0]; }// 替换根元素，并重新heapify public void setRoot(int root) { data[0] = root; heapify(0); } }public static int[] topK(int[] a, int k) { if (a == null || k >= a.length) { return a; }// 先取K个元素放入一个数组topK中 int[] topK = new int[k]; for (int i = 0; i < k; i++) { topK[i] = a[i]; }// 转换成最小堆 MinHeap heap = new MinHeap(topK); // 从k开始，遍历data for (int i = k; i < a.length; i++) { int root = heap.getRoot(); // 当数据小于堆中最小的数（根节点）时，替换堆中的根节点，再转换成堆 if (a[i] < root) { heap.setRoot(a[i]); } }return topK; }

4. 二分法 【经典TopK的各种解法】首先查找 max 和 min，然后计算出mid = (max + min) / 2。实质是寻找最大的K个数中最小的一个。
但是这种方法在实际应用中效果不佳，所以此处不再贴代码。
5. Hash法先通过Hash法，把海量数据中的数字去重，如果重复率较高，这样会减少很大的内存用量，从而缩小运算空间，然后通过上面的第二或者第三种方法计算TopK。