#
Heapselect: Kth Greatest Value

/*********************************************************************** * 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--)); } } }