2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Mar 28 '16 at 18:20
  • $\begingroup$ Hint: Don't use the linear-time heap generation. Pretend you needed an online algorithm. $\endgroup$ – Raphael Mar 28 '16 at 18:22
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for you answer! Can you elaborate a bit more on why I don't need to put all numbers encountered in the heap? $\endgroup$ – user119264 Mar 28 '16 at 17:58
  • 1
    $\begingroup$ @user119264 I'd say that's for you to reason out since it's the core argument for why sasha's solution is correct. You did write you only wanted hints, and this is already a lot more. $\endgroup$ – Raphael Mar 28 '16 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.