[20.6] find the largest 1 million numbers in 1 billion numbers

1. Example

[1,2,3,4,5,6,7,8,9]

find 3 largest
[7,8,9]


2. Implementation

Approach1: Sorting, Time:O( n log n)

Sort the elements and then take the first million from that.  

Approach2: Max Heap, TimeO( n log m), n numbers and each heapify O( log m)

1. Create a Min Heap with the first million numbers
2. For each remaining number, insert it in the Min Heap and then delete the minimum value from the heap
3. The heap now contains the largest million numbers
4. This algorithm is O( n log m ), where m is the number of vlaues we are looking for

Approach3: Selection Rank Algorithm, Time:O(n)
Find the ith smallest(or largest) element in an array in expected linear time.

1. Pick a random element in the array and use it as a pivot. Move all elements smaller than that element to one side of the array , and all elments larger than to the other side.
2. If there are exactly i elements on the right, then you find the smallest  element on this side.
3. Otherwise, if the right side is bigger than i, repeat teh algorithm on the right. If the right side is smaller than i, repeat the algorithm on the left for i - right.size()
Given this algorithm,
you can either 
1. Tweak it to use the existing partitions to find the largest i elements (where i = one million)
2 .Or, once you find the ith largest element, run throguh the array again to return all elements greater than or equal to it

3. Similar Ones http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html https://github.com/monkeylyf/interviewjam/blob/master/searching/cap_Find_Largest_k_numbers_in_n_Numbers.java