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