Share the joy
This is the code to get top k values from a input.
- /*
- * Get the Top Largest K values from small heap
- */
- public class TopK {
- public static void main(String[] args) {
- int[] array = {5, 13,10,12,15,11, 8,23, 40, 16, 83, 23, 31, 73, 59, 25, 75};
- findTopK(array, 5);
- }
- public static void findTopK(int[] array, int k){
- int[] heap = new int[k+1];
- heap[0] = k; //use heap[0] to record the length of heap
- for(int i=0;i
- heapPut(heap, array[i]);
- }
- printArray(heap);
- }
- /*
- * Small heap, put value in heap
- */
- public static void heapPut(int[] heap, int value){
- if(heap==null){
- return;
- }
- if(value>heap[1]){
- heap[1] = value;
- heapAdjust(heap, 1);
- }
- }
- /*
- * Small heap, put value in heap
- */
- public static void heapAdjust(int[] heap, int pos){
- if(heap==null||pos*2>heap[0]){ //heap is empty, or the position is not correct
- return;
- }
- if(heap[pos]<=heap[pos*2]&&(heap[0]==pos*2||heap[pos]<=heap[pos*2+1])){
- //the heap[pos] is already smallest
- //heap[0]==pos*2 is to check if pos has right child. If it doesn’t has right child, then don’t compare with right child.
- return;
- }
- int minPos = (heap[0]==pos*2)?pos*2:heap[pos*2]//heap[pos] is not the smallest, get the min pos
- arrayExchange(heap, pos, minPos);
- heapAdjust(heap, minPos);
- }
- /*
- * Exchange pos1 and pos2 in array[]
- */
- public static void arrayExchange(int[] array, int pos1, int pos2){
- if(array==null||pos1>array.length-1||pos2>array.length-1){
- return;
- }
- int tmp = array[pos1]; array[pos1] = array[pos2]; array[pos2] = tmp;
- return;
- }
- public static void printArray(int[] array){
- if(array==null){
- return;
- }
- for(int i=1;i
- System.out.print(array[i]+” “);
- }
- System.out.println();
- }
- }