面试题中经常用到堆，这里总结一下。
方法一：对源数据中所有数据进行排序，取出前K个数据，就是TopK。
但是当数据量很大时，只需要k个最大的数，整体排序很耗时，效率不高。
方法二：维护一个K长度的数组a[]，先读取源数据中的前K个放入数组，对该数组进行升序排序，再依次读取源数据第K个以后的数据，和数组中最小的元素（a[0]）比较，如果小于a[0]直接pass，大于的话，就丢弃最小的元素a[0]，利用二分法找到其位置，然后该位置前的数组元素整体向前移位，直到源数据读取结束。
这比方法一效率会有很大的提高，但是当K的值较大的时候，长度为K的数据整体移位，也是非常耗时的。
对于这种问题，效率比较高的解决方法是使用最小堆。
首先建立堆
public class Heap { private int[] data; public Heap(int[] data){ this.data=data; buildHeap(); } public void buildHeap() { for ( int i = data.length/ 2- 1; i>= 0; i--) { heapity(i); } } public void heapity(int i) { int left=getLeft(i); int right=getRight(i); int smallIndex=i; if(left<data.length&&data[left]<data[i]) smallIndex=left; if(right<data.length&&data[right]<data[smallIndex]) smallIndex=right; if(smallIndex==i) return; swap(i, smallIndex); heapity(smallIndex); } public int getLeft(int i){ return ((i+ 1)<< 1)- 1; } public int getRight(int i){ return (i+ 1)<< 1; } public void swap(int i,int j){ data[i]^=data[j]; data[j]^=data[i]; data[i]^=data[j]; } public int getMin(){ return data[ 0]; } public void setMin(int i){ data[ 0]=i; heapity( 0); } } 测试 public class TopK { private static int[] topK( int[] data, int k){ int topk[]= new int[k]; for ( int i = 0; i < k; i++) { topk[i]=data[i]; } Heap heap= new Heap(topk); for ( int j = k; j < data.length; j++) { int min=heap.getMin(); if(data[j]>min) heap.setMin(data[j]); } return topk; } public static void main(String[] args) { int[] data = { 33, 86, 59, 46, 84, 76, 1236, 963}; int[] topk=topK(data, 3); for ( int i : topk) { System.out.print(i+ ","); } } }