A heap based problem I have been struggling with this question from my problem set. I do not want a solution but some hints on how to proceed.


  You are given a file of numbers which represent the values of associated with
  certain chemical reactions for the past year from a large scale industrial laboratory (reactions 
   can happen on the millisecond scale, so this file is very large). Let $n$
  represent the number of values in the file. For some fixed $k$, devise
  a $\mathcal{O}(n \log k)$ time algorithm for finding the highest $k$
  reactions that occur in the file.


$\textbf{My approach:}$ I reasoned that I should build a max-heap and exploit the get-max() queries and save the $k$ highest values to an array. The time complexity to build a heap is $\mathcal{O}(n)$ and here mentions the extract-max query is $\mathcal{O}(\log n)$ so this operation would run in $\mathcal{O}(n\log n)$ time and not $\mathcal{O}(n\log k)$? Also, I'm not sure why extract-max runs in $\mathcal{O}(\log n)$ time?
You don't need to put all numbers encountered in the heap. Never let your heap grow in size more than $k$. Keep a min heap. Now, if at some point of time heap has size $ &lt; k$, then push the number encountered ( say $i$ ) into the heap. If heap is full and the number $i$ is greater than top element of heap ( say $top$ ) , pop the $top$ and insert $i$ into heap. At the end all the numbers in the heap are your desired $k$ numbers. Each operation takes $O(logk)$ steps ( as heap size is always $ \le k$ ). And there are $n$ steps so $O(nlogk)$.