5. Selection and Order Statistics
Selection and order-statistics: quickselect, median-of-medians, streaming top-k, heavy hitters, reservoir sampling, and quantile summaries.
Tag
Order-Statistics
13 notes
Multi Selection
Select multiple order statistics in one pass more efficiently than repeated selection.
Upper Median Selection
Select the upper median, the element at index floor(n/2), using selection or partitioning.
Lower Median Selection
Select the lower median, the element at index floor((n-1)/2), using selection or partitioning.
Weighted Median
Select an element whose total weight on each side is at most half of the total weight.
Order Statistic Tree Rank
Compute the sorted-order rank of a key in a search tree augmented with subtree sizes.
Order Statistic Tree Select
Select the element with a given rank from a balanced search tree augmented with subtree sizes.
Quickselect
Select the k-th smallest element in an unsorted array using partitioning.
Bottom K Selection
Select the k smallest elements using bounded structures or partitioning.
Partial Sort Selection
Select the k-th element by partially sorting only the needed prefix of the array.
Heap Select
Select the k-th smallest or largest element by maintaining a heap of candidate values.
Median of Medians
Choose a pivot with guaranteed quality by taking the median of group medians.
Deterministic Select
Selection algorithm with guaranteed linear time using structured pivot choice.