import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
/**
 * Implementation of finding top 100 elements out of a huge int array. <br>
 * 
 * There is an array of 10000000 different int numbers. Find out its largest 100
 * elements. The implementation should be optimized for executing speed. <br>
 * 
 * Note: This is the third version of implementation, this time I make the best out
 * of the heap sort algorithm by using a minimum heap. The heap maintains the top biggest
 * numbers that guarantees the minimum number is removed every time a new number is added
 * to the heap. It saves memory usage to the limit by just using an array which size is 101
 * and a few temp elements. However, the performance is not as good as the bit map way but 
 * better than the multiple thread way. 
 * 
 * @author zhangxu04
 */
public class FindTopElements3 {
 
	private static final int ARRAY_LENGTH = 10000000; // big array length
 
	public static void main(String[] args) {
		FindTopElements3 fte = new FindTopElements3();
 
		// Get a array which is not in order and elements are not duplicate
		int[] array = getShuffledArray(ARRAY_LENGTH);
 
		// Find top 100 elements and print them by desc order in the console
		long start = System.currentTimeMillis();
		fte.findTop100(array);
		long end = System.currentTimeMillis();
		System.out.println("Costs " + (end - start) + "ms");
	}
 
	public void findTop100(int[] arr) {
		MinimumHeap heap = new MinimumHeap(100);
		for (Integer i : arr) {
			heap.add(i);
			if (heap.size() > 100) {
				heap.deleteTop();
			}
		}
		for (int i = 0; i < 100; i++) {
			System.out.println(heap.deleteTop());
		}
	}
 
	/**
	 * Get shuffled int array
	 * 
	 * @return array not in order and elements are not duplicate
	 */
	private static int[] getShuffledArray(int len) {
		System.out
				.println("Start to generate test array... this may take several seconds.");
		List<Integer> list = new ArrayList<Integer>(len);
		for (int i = 0; i < len; i++) {
			list.add(i);
		}
		Collections.shuffle(list);
 
		int[] ret = new int[len];
		for (int i = 0; i < len; i++) {
			ret[i] = list.get(i);
		}
		return ret;
	}
 
}
 
class MinimumHeap {
 
	int[] items;
	int size;
 
	public MinimumHeap(int size) {
		items = new int[size + 1];
		size = 0;
	}
 
	void shiftUp(int index) {
		int intent = items[index];
		while (index > 0) {
			int pindex = (index - 1) / 2;
			int parent = items[pindex];
			if (intent < parent) {
				items[index] = parent;
				index = pindex;
			} else {
				break;
			}
		}
		items[index] = intent;
	}
 
	void shiftDown(int index) {
		int intent = items[index];
		int leftIndex = 2 * index + 1;
		while (leftIndex < size) {
			int minChild = items[leftIndex];
			int minIndex = leftIndex;
 
			int rightIndex = leftIndex + 1;
			if (rightIndex < size) {
				int rightChild = items[rightIndex];
				if (rightChild < minChild) {
					minChild = rightChild;
					minIndex = rightIndex;
				}
			}
 
			if (minChild < intent) {
				items[index] = minChild;
				index = minIndex;
				leftIndex = index * 2 + 1;
			} else {
				break;
			}
		}
		items[index] = intent;
	}
 
	public void add(int item) {
		items[size++] = item;
		shiftUp(size - 1);
	}
 
	public int deleteTop() {
		if (size < 1) {
			return 0;
		}
		int maxItem = items[0];
		int lastItem = items[size - 1];
		size--;
		if (size < 1) {
			return lastItem;
		}
		items[0] = lastItem;
		shiftDown(0);
		return maxItem;
	}
 
	public boolean isEmpty() {
		return size < 1;
	}
 
	public int size() {
		return size;
	}
 
	/**
	 * MinimumHeap main test
	 * @param args
	 */
	public static void main(String[] args) {
		MinimumHeap heap = new MinimumHeap(7);
		heap.add(2);
		heap.add(3);
		heap.add(5);
		heap.add(1);
		heap.add(4);
		heap.add(7);
		heap.add(6);
 
		heap.deleteTop();
		heap.deleteTop();
 
		while (!heap.isEmpty()) {
			System.out.println(heap.deleteTop());
		}
	}
 
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.CompletionService;
import java.util.concurrent.ExecutorCompletionService;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
 
/**
 * Implementation of finding top 100 elements out of a huge int array. <br>
 * 
 * There is an array of 10000000 different int numbers. 
 * Find out its largest 100 elements. 
 * The implementation should be optimized for executing speed.
 * 
 * @author zhangxu04
 */
public class FindTopElements {
 
	private static final int ARRAY_LENGTH = 10000000; // big array length
	private static final int ELEMENT_NUM_PER_GROUP = 10000; // split big array into sub-array, this represents sub-array length
	private static final int TOP_ELEMENTS_NUM = 100; // top elements number
 
	private ExecutorService executorService;
 
	private CompletionService<int[]> completionService;
 
	public FindTopElements() {
		int MAX_THREAD_COUNT = 50;
		executorService = Executors.newFixedThreadPool(MAX_THREAD_COUNT);
		completionService = new ExecutorCompletionService<int[]>(executorService);
	}
 
	/**
	 * Start from here :-)
	 * @param args
	 */
	public static void main(String[] args) {
		FindTopElements findTopElements = new FindTopElements();
 
		// Get a array which is not in order and elements are not duplicate
		int[] array = getShuffledArray(ARRAY_LENGTH);
 
		// Find top 100 elements and print them by desc order in the console
		long start = System.currentTimeMillis();
		findTopElements.findTop100(array);
		long end = System.currentTimeMillis();
		System.out.println("Costs " + (end - start) + "ms");
	}
 
	/**
	 * Leveraging concurrent components of JDK, we can deal small parts of the huge array concurrently.
	 * The huge array are split into several sub arrays which are submitted to a thread pool one by one.
	 * By using <code>CompletionService</code>, we can take out completed result from the pool as soon as possible, 
	 * which avoid the block issue when getting future result through a future task list by using 
	 * <code>ExcutorService</code> and <code>Future</code> class. Moreover, the can optimize the performance of 
	 * the piece of code by processing the completed results once we get them, so the overall sort invocation will 
	 * not be delayed to the final moment.
	 * 
	 */
	private void findTop100(int[] arr) {
		System.out.println("Start to compute.");
		int groupNum = (ARRAY_LENGTH / ELEMENT_NUM_PER_GROUP);
		System.out.println("Split " + ARRAY_LENGTH + " elements into " + groupNum + " groups");
		for (int i = 0; i < groupNum; i++) {
			int[] toBeSortArray = new int[ELEMENT_NUM_PER_GROUP];
			System.arraycopy(arr, i * ELEMENT_NUM_PER_GROUP, toBeSortArray, 0, ELEMENT_NUM_PER_GROUP);
			completionService.submit(new FindTop100(toBeSortArray));
		}
 
		try {
			int[] overallArray = new int[TOP_ELEMENTS_NUM * groupNum];
			for (int i = 0; i < groupNum; i++) {
				System.arraycopy(completionService.take().get(), 0, overallArray, i * TOP_ELEMENTS_NUM, TOP_ELEMENTS_NUM);
			}
			Arrays.sort(overallArray);
			for (int i = 1; i <= TOP_ELEMENTS_NUM; i++) {
				System.out.println(overallArray[TOP_ELEMENTS_NUM * groupNum - i]);
			}
			System.out.println("Finish to output result.");
		} catch (Exception e) {
			e.printStackTrace();
		}
		executorService.shutdown();
	}
 
	/**
	 * Callable of finding top 100 elements <br>
	 * The steps are as below:
	 * 1) Quick sort a array
	 * 2) Get reverse 100 elements and put them into a new array
	 * 3) return the new array
	 */
	private class FindTop100 implements Callable<int[]> {
 
		private int[] array;
 
		public FindTop100(int[] array) {
			this.array = array;
		}
 
		@Override
		public int[] call() throws Exception {
			int len = array.length;
			Arrays.sort(array);
			int[] result = new int[TOP_ELEMENTS_NUM];
			int index = 0;
			for (int i = 1; i <= TOP_ELEMENTS_NUM; i++) {
				result[index++] = array[len - i];
			}
			return result;
		}
 
	}
 
	/**
	 * Get shuffled int array
	 * 
	 * @return array not in order and elements are not duplicate
	 */
	private static int[] getShuffledArray(int len) {
		System.out.println("Start to generate test array... this may take several seconds.");
		List<Integer> list = new ArrayList<Integer>(len);
		for (int i = 0; i < len; i++) {
			list.add(i);
		}
		Collections.shuffle(list);
 
		int[] ret = new int[len];
		for (int i = 0; i < len; i++) {
			ret[i] = list.get(i);
		}
		return ret;
	}
 
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
/**
 * Implementation of finding top 100 elements out of a huge int array. <br>
 * 
 * There is an array of 10000000 different int numbers. Find out its largest 100
 * elements. The implementation should be optimized for executing speed. <br>
 * 
 * Note: This is the second version of implementation, the previous one using 
 * thread pool provided by JDK concurrent toolkit is not efficient enough, the 
 * second version is an enhanced one based on bit map algorithm, which is estimated to
 * have at least a 3 times faster and consume less memory usage.
 * 
 * @author zhangxu04
 */
public class FindTopElements2 {
 
	private static final int ARRAY_LENGTH = 10000000; // big array length
 
	public static void main(String[] args) {
		FindTopElements2 fte = new FindTopElements2(ARRAY_LENGTH + 1);
 
		// Get a array which is not in order and elements are not duplicate
		int[] array = getShuffledArray(ARRAY_LENGTH);
 
		// Find top 100 elements and print them by desc order in the console
		long start = System.currentTimeMillis();
		fte.findTop100(array);
		long end = System.currentTimeMillis();
		System.out.println("Costs " + (end - start) + "ms");
	}
 
	private final int[] bitmap;
 
	private final int size;
 
	public FindTopElements2(final int size) {
		this.size = size;
		int len = ((size % 32) == 0) ? size / 32 : size / 32 + 1;
		this.bitmap = new int[len];
	}
 
	private static int index(final int number) {
		return number / 32;
	}
 
	private static int position(final int number) {
		return number % 32;
	}
 
	private void adjustBitMap(final int index, final int position) {
		int bit = bitmap[index] | (1 << position);
		bitmap[index] = bit;
	}
 
	public void add(int[] numArr) {
		for (int i = 0; i < numArr.length; i++) {
			add(numArr[i]);
		}
	}
 
	public void add(int number) {
		adjustBitMap(index(number), position(number));
	}
 
	public boolean getIndex(final int index) {
		if (index > size) {
			return false;
		}
 
		int bit = (bitmap[index(index)] >> position(index)) & 0x0001;
		return (bit == 1);
	}
 
	private void findTop100(int[] arr) {
		System.out.println("Start to compute.");
		add(arr);
		int[] result = new int[100];
		int index = 0;
		for (int i = bitmap.length - 1; i >= 0; i--) {
			for (int j = 31; j >= 0; j--) {
				if (((bitmap[i] >> j) & 0x0001) == 1) {
					if (index == result.length) {
						break;
					}
					result[index++] = ((i) * 32) + j ;
				}
			}
			if (index == result.length) {
				break;
			}
		}
 
		for (int j = 0; j < result.length; j++) {
			System.out.println(result[j]);
		}
		System.out.println("Finish to output result.");
	}
 
	/**
	 * Get shuffled int array
	 * 
	 * @return array not in order and elements are not duplicate
	 */
	private static int[] getShuffledArray(int len) {
		System.out.println("Start to generate test array... this may take several seconds.");
		List<Integer> list = new ArrayList<Integer>(len);
		for (int i = 0; i < len; i++) {
			list.add(i);
		}
		Collections.shuffle(list);
 
		int[] ret = new int[len];
		for (int i = 0; i < len; i++) {
			ret[i] = list.get(i);
		}
		return ret;
	}
 
}