Maintain a min-heap with size = k, to collect the result.
1 //Find K minimum values from an unsorted array 2 //Implement Min-Heap 3 4 public int[] findKMax(int[] arr, int k){ 5 if(arr == null || arr.length == 0) return null; 6 int[] result = new int[k]; 7 for(int i = 0; i < k; i ++) 8 result[i] = arr[i]; 9 buildMinHeap(result); 10 for(int i = k; i < arr.length; i ++){ 11 if(arr[i] > result[0]){ 12 result[0] = arr[i]; 13 minHeapify(result, 0); 14 } 15 } 16 return result; 17 } 18 19 public void buildMinHeap(int[] arr){ 20 for(int i = arr.length / 2 - 1; i > -1; i --){//bottom-up build min heap 21 minHeapify(arr, i); 22 } 23 } 24 25 public void minHeapify(int[] arr, int curIndex){ 26 int left = curIndex * 2 + 1; 27 int right = curIndex * 2 + 2; 28 int smallest = curIndex; 29 if(left < arr.length && arr[left] < arr[smallest]) 30 smallest = left; 31 if(right < arr.length && arr[right] < arr[smallest]) 32 smallest = right; 33 if(smallest != curIndex){ 34 swap(arr, smallest, curIndex); 35 minHeapify(arr,smallest); 36 } 37 } 38 39 public void swap(int[] arr, int aa, int bb){ 40 int tmp = arr[aa]; 41 arr[aa] = arr[bb]; 42 arr[bb] = tmp; 43 }