title: The Most Efficient Way To Find Top K Frequent Words In A Big Word Sequence
body: <p>Input: A positive integer K and a big text. The text can actually be viewed as word sequence. So we don't have to worry about how to break down it into word sequence.<br>
  Output: The most frequent K words in the text.</p>
  
  <p>My thinking is like this. </p>
  
  <ol>
  <li><p>use a Hash table to record all words' frequency while traverse the whole word sequence. In this phase, the key is "word" and the value is "word-frequency". This takes O(n) time. </p></li>
  <li><p>sort the (word, word-frequency) pair; and the key is "word-frequency". This takes O(n*lg(n)) time with normal sorting algorithm. </p></li>
  <li><p>After sorting, we just take the first K words. This takes O(K) time. </p></li>
  </ol>
  
  <p>To summarize, the total time is O(n+n<em>lg(n)+K)， Since K is surely smaller than N, so it is actually O(n</em>lg(n)).</p>
  
  <p>We can improve this. Actually, we just want top K words. Other words' frequency is not concern for us. So, we can use "partial Heap sorting". For step 2) and 3), we don't just do sorting. Instead, we change it to be</p>
  
  <p>2') build a heap of (word, word-frequency) pair with "word-frequency" as key. It takes O(n) time to build a heap;</p>
  
  <p>3') extract top K words from the heap. Each extraction is O(lg(n)). So, total time is O(k*lg(n)).</p>
  
  <p>To summarize, this solution cost time O(n+k*lg(n)).</p>
  
  <p>This is just my thought. I haven't find out way to improve step 1).<br>
  I Hope some Information Retrieval experts can shed more light on this question.</p>