Return top k values from an array of length N

Best solution: We can use the heap of length k to store the top k values. The smallest value Y is on the top of the heap. When considering a new value X, if X <= Y, we don't need to change the original heap. If X > Y, X should replace Y on the heap and then we need to update the heap again. The update algorithm is O(logK).

The time of this algorithm is O(n*logK).

The definition of the heap: http://en.wikipedia.org/wiki/Heap_(data_structure)

How to update the min-heap:


If N is positive integer, the range is not very big. We can consider use extra space counte[MAXN] to record the frequency of the integer, then pick up the top k frequency numbers.