find K maximum value from an unsorted array(implement min heap)

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 }
原文地址:https://www.cnblogs.com/reynold-lei/p/4370939.html