# 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?

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Mar 28 '16 at 18:20
• Hint: Don't use the linear-time heap generation. Pretend you needed an online algorithm. – Raphael Mar 28 '16 at 18:22

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 $< 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)$.