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