Content deleted Content added
new problem statement section |
|||
Line 37:
When data is already organized into a [[data structure]], it may be possible to perform selection in an amount of time that is sublinear in the number of values. As a simple case of this, for data already sorted into an array, selecting the <math>k</math> element may be performed by a single array lookup, in constant time.
For data organized as a [[binary heap]], or more generally as a heap-ordered tree (a tree in which each node stores a value and has a bounded number of children, all having larger values), it is possible to perform selection in time <math>O(k)</math>, independent of the size <math>n</math> of the whole tree, and faster than the <math>O(k\log n)</math> time bound that would be obtained from [[best-first search]]. This heap selection method has been applied to several problems of listing multiple solutions to combinatorial optimization problems, such as finding the [[k shortest path routing|{{mvar|k}} shortest paths]] in a weighted graph, by defining a [[State space (computer science)|state space]] of solutions in the form of an [[implicit graph|implicitly defined]] heap-ordered tree, and then applying this selection algorithm to this tree.
For a collection of data values undergoing dynamic insertions and deletions, it is possible to augment a [[self-balancing binary search tree]] structure with a constant amount of additional information per tree node, allowing insertions, deletions, and selection queries that ask for the <math>k</math>th element in the current set to all be performed in <math>O(\log n)</math> time per operation.{{r|clrs}}
| |||