Heapselect: Kth Greatest Value
by Isai Damier, Android Engineer @ Google

/***********************************************************************
 * Author: Isai Damier
 * Title: Find Kth Greatest Value
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a list of values, find the kth top score. Assume the highest
 *   score is the 1st not the 0th.
 *
 * Time Complexity: O(n log n)
 * 
 * Sample Input: {21,3,34,5,13,8,2,55,1,19}; 4
 * Sample Output: 19
 * 
 * Technical Details: This is a selection algorithm, where the task is
 *   to select an elite out of a group. In the sample input, for instance,
 *   we are to select the 4th greatest number in the list; which happens
 *   to be 13 since 55, 34, and 21 are all greater than 13.
 * 
 *   Generally, selection algorithms are modified sort algorithms; where
 *   instead of sorting the whole list, we sort up to the kth value.
 *   Hence, a selection algorithm is bounded by whatever sort algorithm
 *   is used to implement it.
 * 
 *   Here for example we are using heapselect to find the kth largest
 *   value. Consequently, this algorithm is bounded by heapsort; leading
 *   to a worse case time complexity of O( n log n).
 * 
 *   Note: Finding the kth largest is essentially the same as finding
 *   the kth smallest.
 * 
 *   If you really want to reduce the call to moveDown() you can use
 *   the following code instead:
 * 
 *     int limit = last - k;
 *     int i = last;
 *     for (; i > limit; i--) 
 *       if (A[0] > A[i]) {
 *         swap(A, 0, i);
 *         moveDown(A, 0, i - 1);
 *       }
 *     return A[i+1];
 *   
 **********************************************************************/ 
 public int heapselect(int A[], int k) {
  int last = A.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(A, i, last);
  }
  //sort up to k (i.e. find the kth)
  int limit = last - k + 1;
  for (int i = last; i > limit; i--) {
    if (A[0] > A[i]) {
      swap(A, 0, i);
      moveDown(A, 0, i - 1);
    }
  }
  return A[0];
}//findKthLargest(int[], int)

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 Heapselect method, of class SearchAlgorithms.
   */
  @Test
  public void testHeapselect() {
    System.out.println("heapselect");
    int[] A = {21, 3, 34, 5, 13, 8, 2, 55, 1, 19};
    SearchAlgorithms search = new SearchAlgorithms();
    int expResult[] = {1, 2, 3, 5, 8, 13, 19, 21, 34, 55};
    int k = expResult.length;
    for (int exp:expResult) {
      assertEquals(exp, search.heapselect(A, k--));
    }
  }
}