Heapselect: Find the Top k values
by Isai Damier, Android Engineer @ Google

/***********************************************************************
 * Author: Isai Damier
 * Title: Find the Greatest k values
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a list of values, find the top k values.
 *
 * Time Complexity: O(n log n)
 * 
 * Sample Input: {21,3,34,5,13,8,2,55,1,19}; 4
 * Sample Output: {19,21,34,55}
 * 
 * Technical Details: This selection problem is a classic and so has
 *   many very good solutions. In fact, any sorting algorithm can be
 *   modified to solve this problem. In the worst case, the problem
 *   can indeed be reduced to a sorting problem: where the collection
 *   is first sorted and then the element at indices 0 to k-1 are
 *   retrieved.
 *   
 *   Presently the problem is solved using a modified version of
 *   heapsort called heapselect.
 **********************************************************************/ 
 public int[] heapselectTopK(int[] G, int k) {
  int last = G.length - 1;
  //convert array to heap in O(n)
  int youngestParent = last / 2;//l = 2*p+1: p=(l-1)/2
  for (int i = youngestParent; i >= 0; i--) {
    moveDown(G, i, last);
  }
  //sort up to k (i.e. find the kth)
  int limit = last - k;
  for (int i = last; i > limit; i--) {
    if (G[0] > G[i]) {
      swap(G, 0, i);
      moveDown(G, 0, i - 1);
    }
  }
  return Arrays.copyOfRange(G, G.length - k, G.length);
}

private void moveDown(int[] A, int first, int last) {
  int largest = 2 * first + 1;
  while (largest <= last) {
    if (largest < last && A[largest] < A[largest + 1]) {
      largest++;
    }
    if (A[first] < A[largest]) {
      swap(A, first, largest);
      first = largest;
      largest = 2 * first + 1;
    } else {
      return;
    }
  }
}
package algorithms;

import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class SearchAlgorithmsTest {
  
  /**
   * Test of heapselectTopK method, of class SearchAlgorithms.
   */
  @Test
  public void testHeapselectTopKInOrder() {
    System.out.println("heapselectTopK");
    int[] G = {21, 3, 34, 5, 13, 8, 2, 55, 1, 19};
    int k = 10;//[1, 2, 3, 5, 8, 13, 19, 21, 34, 55]
    SearchAlgorithms search = new SearchAlgorithms();
    int[][] expResult = {{55},
                         {34, 55},
                         {21, 34, 55},
                         {19, 21, 34, 55},
                         {13, 19, 21, 34, 55},
                         {8, 13, 19, 21, 34, 55},
                         {5, 8, 13, 19, 21, 34, 55},
                         {3, 5, 8, 13, 19, 21, 34, 55},
                         {2, 3, 5, 8, 13, 19, 21, 34, 55},
                         {1, 2, 3, 5, 8, 13, 19, 21, 34, 55}
    };
    for (int[] exp : expResult) {
      assertArrayEquals(exp, search.heapselectTopK(G, exp.length));
    }
  }
}