题目：给定一个无序整数数组arr,找到其中最小的k个数

要求:如果数组arr的长度为n，排序之后自然可以得到最小的k个数，此时时间复杂度与排序的时间复杂度相同均为O（NlogN）,本题要求实现时间复杂度为O(NLogK).

1.O(NLogK)的方法，即一直维护一个有k个数的最大的大根堆，这个堆是目前选出的k个最小数，在堆里的k个元素中堆顶的元素是最大的一个。

接下来遍历整个数组，遍历的过程中看当前数是否比堆顶元素小。如果是，就把堆顶的元素替换成当前的数，然后从堆顶的位置调整堆，替换后堆的最大元素的位置依旧在堆顶；如果不是，则不进行任何操作，继续遍历下一个数；遍历完成后，堆中的k个数就是所有数组中最小的k个数。

具体请参看如下代码中的getMinKNumsByHeap方法，代码中的heapInsert和heapify方法分别为堆排序中的建堆和调整堆的实现。

1 public int[]  getMinKNumsByHeap(int[] arr,int k) 2 { 3     if(k<1 || k>arr.length) 4             return arr; 5     int[] kHeap=new int[k]; 6     for(int i=0;i
      
       arr[index])45              largest=left;46      if(right
       
        arr[largest])47               largest=right;48      if(largest!=index)49               swap(arr,largest,index);50       else51         break;52     index=largest;53     left=index*2+1;54     right=index*2+2;55     }56 }57 58 public void swap(int[] arr,int index1,int index2)59 {60     int tmp=arr[index1];61     arr[index1]=arr[index2];62     arr[index2]=tmp;63 }