# Find TopK value, by small heap

By | November 30, 2014
Share the joy
•
•
•
•
•
•

This is the code to get top k values from a input.

1. /*
2.  * Get the Top Largest K values from small heap
3.  */
4. public class TopK {
5.     public static void main(String[] args) {
6.         int[] array = {5, 13,10,12,15,11, 8,23, 40, 16, 83, 23, 31, 73, 59, 25, 75};
7.         findTopK(array, 5);
8.     }
9.     public static void findTopK(int[] array, int k){
10.         int[] heap = new int[k+1];
11.         heap[0] = k;     //use heap[0] to record the length of heap
12.         for(int i=0;i
13.             heapPut(heap, array[i]);
14.         }
15.         printArray(heap);
16.     }
17.     /*
18.      * Small heap, put value in heap
19.      */
20.     public static void heapPut(int[] heap, int value){
21.         if(heap==null){
22.             return;
23.         }
24.         if(value>heap[1]){
25.             heap[1] = value;
27.         }
28.     }
29.     /*
30.      * Small heap, put value in heap
31.      */
32.     public static void heapAdjust(int[] heap, int pos){
33.         if(heap==null||pos*2>heap[0]){    //heap is empty, or the position is not correct
34.             return;
35.         }
36.         if(heap[pos]<=heap[pos*2]&&(heap[0]==pos*2||heap[pos]<=heap[pos*2+1])){
37.         //the heap[pos] is already smallest
38.      //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.
39.             return;
40.         }
41.         int minPos = (heap[0]==pos*2)?pos*2:heap[pos*2]//heap[pos] is not the smallest, get the min pos
42.         arrayExchange(heap, pos, minPos);
44.     }
45.     /*
46.      * Exchange pos1 and pos2 in array[]
47.      */
48.     public static void arrayExchange(int[] array, int pos1, int pos2){
49.         if(array==null||pos1>array.length-1||pos2>array.length-1){
50.             return;
51.         }
52.         int tmp = array[pos1];    array[pos1] = array[pos2]; array[pos2] = tmp;
53.         return;
54.     }
55.     public static void printArray(int[] array){
56.         if(array==null){
57.             return;
58.         }
59.         for(int i=1;i
60.             System.out.print(array[i]+” “);
61.         }
62.         System.out.println();
63.     }
64. }