2 ms·
Ask HN: Solve algorithm question from “The Algorithm Design Manual” Q. 4-12?
Devise an algorithm for finding the k smallest elements of an unsorted set of n
integers in O(n + k log n)
Question 4-12 in "The Algorithm Design Manual" by Skienna. We could not agree with the solution in the solutions manual.
- drallison 11y agoThe solution on the solutions wiki solves the problem by building a heap data structure and then removing the k smallest elements. That seems to be correct. Why do you believe this to be incorrect?