5. Selection and Order Statistics

Selection and order-statistics: quickselect, median-of-medians, streaming top-k, heavy hitters, reservoir sampling, and quantile summaries.

35 items

5. Selection and order statistics, 35

index slug name
116 quickselect Quickselect
117 randomized-quickselect Randomized Quickselect
118 deterministic-select Deterministic Select
119 median-of-medians Median of Medians
120 introselect Introselect
121 heap-select Heap Select
122 partial-sort-selection Partial Sort Selection
123 nth-element Nth Element
124 top-k-by-heap Top K by Heap
125 top-k-by-quickselect Top K by Quickselect
126 bottom-k-selection Bottom K Selection
127 streaming-top-k Streaming Top K
128 streaming-heavy-hitters Streaming Heavy Hitters
129 misra-gries Misra Gries
130 space-saving-algorithm Space Saving Algorithm
131 count-min-sketch-query Count Min Sketch Query
132 median-maintenance-two-heaps Median Maintenance by Two Heaps
133 order-statistic-tree-select Order Statistic Tree Select
134 order-statistic-tree-rank Order Statistic Tree Rank
135 weighted-median Weighted Median
136 lower-median-selection Lower Median Selection
137 upper-median-selection Upper Median Selection
138 multi-selection Multi Selection
139 selection-in-sorted-matrix Selection in Sorted Matrix
140 kth-smallest-in-two-sorted-arrays Kth Smallest in Two Sorted Arrays
141 kth-smallest-pair-distance Kth Smallest Pair Distance
142 kth-smallest-subarray-sum Kth Smallest Subarray Sum
143 kth-smallest-fraction Kth Smallest Fraction
144 kth-largest-stream Kth Largest in Stream
145 reservoir-sampling Reservoir Sampling
146 weighted-reservoir-sampling Weighted Reservoir Sampling
147 floyd-sampling Floyd Sampling
148 sample-sort-selection Sample Sort Selection
149 quantile-summary Quantile Summary
150 greenwald-khanna-quantile Greenwald Khanna Quantile
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Quickselect

Select the k-th smallest element in an unsorted array using partitioning.
algorithms selection quickselect order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Randomized Quickselect

Quickselect with random pivot selection to achieve robust expected linear time.
algorithms selection randomized quickselect
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Deterministic Select

Selection algorithm with guaranteed linear time using structured pivot choice.
algorithms selection deterministic order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Median of Medians

Choose a pivot with guaranteed quality by taking the median of group medians.
algorithms selection median-of-medians order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Introselect

Hybrid selection algorithm that combines Quickselect with worst-case fallback.
algorithms selection introselect hybrid
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Heap Select

Select the k-th smallest or largest element by maintaining a heap of candidate values.
algorithms selection heap order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Partial Sort Selection

Select the k-th element by partially sorting only the needed prefix of the array.
algorithms selection partial-sort order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Nth Element

Rearrange an array so that the element at position k is the same as in sorted order, with partition guarantees.
algorithms selection nth-element partition
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Top K by Heap

Find the k largest or k smallest elements by maintaining a bounded heap.
algorithms selection top-k heap
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Top K by Quickselect

Find the k largest elements using partition-based selection in linear time.
algorithms selection top-k quickselect
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Bottom K Selection

Select the k smallest elements using bounded structures or partitioning.
algorithms selection bottom-k order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Streaming Top K

Maintain the k largest elements while values arrive one at a time.
algorithms selection streaming top-k heap
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Streaming Heavy Hitters

Find frequent items in a stream using bounded memory.
algorithms selection streaming heavy-hitters frequency
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Misra Gries

Find frequent items in a stream by maintaining a bounded set of counters.
algorithms streaming heavy-hitters frequency
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Space Saving

Approximate frequent items in a stream with tighter error bounds than Misra Gries.
algorithms streaming heavy-hitters approximate
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Count Min Sketch Query

Estimate item frequencies in a stream using a compact hash based summary.
algorithms streaming frequency count-min-sketch approximate
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Median Maintenance

Maintain the median of a stream using a max heap and a min heap.
algorithms streaming median heaps
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Order Statistic Tree Select

Select the element with a given rank from a balanced search tree augmented with subtree sizes.
algorithms selection order-statistics trees
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Order Statistic Tree Rank

Compute the sorted-order rank of a key in a search tree augmented with subtree sizes.
algorithms selection order-statistics trees
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Weighted Median

Select an element whose total weight on each side is at most half of the total weight.
algorithms selection weighted-median order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Lower Median

Select the lower median, the element at index floor((n-1)/2), using selection or partitioning.
algorithms selection median order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Upper Median

Select the upper median, the element at index floor(n/2), using selection or partitioning.
algorithms selection median order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Multi Selection

Select multiple order statistics in one pass more efficiently than repeated selection.
algorithms selection multi-selection order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Sorted Matrix Selection

Select the k-th smallest element from a matrix whose rows and columns are sorted.
algorithms selection matrix binary-search
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Smallest in Two Sorted Arrays

Select the k-th smallest element from two sorted arrays without merging them.
algorithms selection sorted-arrays binary-search
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Smallest Pair Distance

Find the k-th smallest absolute difference among all pairs in an array.
algorithms selection binary-search two-pointers
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Smallest Subarray Sum

Find the k-th smallest sum among all contiguous subarrays, usually for nonnegative arrays.
algorithms selection subarray-sum binary-search
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Smallest Fraction

Select the k-th smallest fraction formed by pairs from a sorted array using heap or binary search.
algorithms selection fractions heap binary-search
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Largest in Stream

Maintain the k-th largest value while values arrive one at a time.
algorithms selection streaming heap
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Reservoir Sampling

Select a uniform random sample from a stream of unknown length using fixed memory.
algorithms sampling streaming randomized
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Weighted Reservoir Sampling

Select a random sample from a stream where each item has a nonnegative weight.
algorithms sampling streaming weighted randomized
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Floyd Sampling

Select k distinct integers uniformly from a fixed range without shuffling the whole range.
algorithms sampling randomized sets
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Sample Sort Selection

Use sampling to approximate order statistics and refine selection efficiently.
algorithms selection sampling approximate
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Quantile Summary

Maintain approximate quantiles of a stream using compact summaries.
algorithms streaming quantiles approximate
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Greenwald Khanna Quantile

Maintain deterministic approximate quantiles of a stream with rank error guarantees.
algorithms streaming quantiles greenwald-khanna