5 ms·
The original article uses heap to get top K numbers. It's runtime complexity is O(N*log(K)) and nth_element is O(N), so the algorithms are not similar at all.
by dzorz 15y ago
The original article uses heap to get top K numbers. It's runtime complexity is O(N*log(K)) and nth_element is O(N), so the algorithms are not similar at all.
- veyron 15y agoscorchin posted the implementation of nth_element, except he forgot to look at how the gnu implementation of __introselect behaves. If you look there, you will see it internally uses a heap.
- dzorz 15y agoIt uses heap only as a fallback if maximum recursion depth is reached. The key difference between __introselect and the posted article is that __introselect uses pivoting to (ideally) "throw" away half of the array during each step.