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;
  26.             heapAdjust(heap, 1);
  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);
  43.         heapAdjust(heap, 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. }