Revision as of 20:40, 12 January 2014 edit Qwertyus (talk \| contribs) Extended confirmed users 31,640 edits →Data structure-based solutions: O((n + k) log k) = O(n log k), and don't address the reader as "you"; wants citation and clarification for the second suggestion ← Previous edit		Revision as of 20:44, 12 January 2014 edit undo Qwertyus (talk \| contribs) Extended confirmed users 31,640 edits →Data structure-based solutions: remove last suggestion, which appears to solve a wholly different problem (selection in a stream, not partial sorting) Next edit →
Line 12: It is possible to transform the list into a [[binary heap]] in Θ(''n'') time, and then traverse the heap using a modified [[breadth-first search]] algorithm that places the elements in a [[priority queue]]{{clarify\|reason=a heap is a priority queue!}} (instead of the ordinary queue that is normally used in a BFS), and terminate the scan after traversing exactly ''k'' elements. As the queue size remains O(''k'') throughout the traversal, it would require O(''k'' log ''k'') time to complete, leading to a time bound of O(''n'' + ''k'' log ''k'') on this algorithm.{{citation needed}} We can achieve an O(log ''n'') time solution using [[skip lists]]. Skip lists are sorted data structures that allow insertion, deletion and indexed retrieval in O(log ''n'') time. Thus, for any given percentile, we can insert a new element into (and possibly delete an old element from) the list in O(log ''n''), calculate the corresponding index(es) and finally access the percentile value in O(log ''n'') time. See, for example, this Python-based implementation for calculating [http://code.activestate.com/recipes/576930-efficient-running-median-using-an-indexable-skipli running median]. == Optimised sorting algorithms ==

Partial sorting: Difference between revisions