5. Selection and Order Statistics – brain

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

Randomized QuickselectQuickselect with random pivot selection to achieve robust expected linear time.

Deterministic SelectSelection algorithm with guaranteed linear time using structured pivot choice.

Median of MediansChoose a pivot with guaranteed quality by taking the median of group medians.

IntroselectHybrid selection algorithm that combines Quickselect with worst-case fallback.

Heap SelectSelect the k-th smallest or largest element by maintaining a heap of candidate values.

Partial Sort SelectionSelect the k-th element by partially sorting only the needed prefix of the array.

Nth ElementRearrange an array so that the element at position k is the same as in sorted order, with partition guarantees.

Top K by HeapFind the k largest or k smallest elements by maintaining a bounded heap.

Top K by QuickselectFind the k largest elements using partition-based selection in linear time.

Bottom K SelectionSelect the k smallest elements using bounded structures or partitioning.

Streaming Top KMaintain the k largest elements while values arrive one at a time.

Streaming Heavy HittersFind frequent items in a stream using bounded memory.

Misra GriesFind frequent items in a stream by maintaining a bounded set of counters.

Space SavingApproximate frequent items in a stream with tighter error bounds than Misra Gries.

Count Min Sketch QueryEstimate item frequencies in a stream using a compact hash based summary.

Median MaintenanceMaintain the median of a stream using a max heap and a min heap.

Order Statistic Tree SelectSelect the element with a given rank from a balanced search tree augmented with subtree sizes.

Order Statistic Tree RankCompute the sorted-order rank of a key in a search tree augmented with subtree sizes.

Weighted MedianSelect an element whose total weight on each side is at most half of the total weight.

Lower MedianSelect the lower median, the element at index floor((n-1)/2), using selection or partitioning.

Upper MedianSelect the upper median, the element at index floor(n/2), using selection or partitioning.

Multi SelectionSelect multiple order statistics in one pass more efficiently than repeated selection.

Sorted Matrix SelectionSelect the k-th smallest element from a matrix whose rows and columns are sorted.

Kth Smallest in Two Sorted ArraysSelect the k-th smallest element from two sorted arrays without merging them.

Kth Smallest Pair DistanceFind the k-th smallest absolute difference among all pairs in an array.

Kth Smallest Subarray SumFind the k-th smallest sum among all contiguous subarrays, usually for nonnegative arrays.

Kth Smallest FractionSelect the k-th smallest fraction formed by pairs from a sorted array using heap or binary search.

Kth Largest in StreamMaintain the k-th largest value while values arrive one at a time.

Reservoir SamplingSelect a uniform random sample from a stream of unknown length using fixed memory.

Weighted Reservoir SamplingSelect a random sample from a stream where each item has a nonnegative weight.

Floyd SamplingSelect k distinct integers uniformly from a fixed range without shuffling the whole range.

Sample Sort SelectionUse sampling to approximate order statistics and refine selection efficiently.

Quantile SummaryMaintain approximate quantiles of a stream using compact summaries.

Greenwald Khanna QuantileMaintain deterministic approximate quantiles of a stream with rank error guarantees.

QuickselectSelect the k-th smallest element in an unsorted array using partitioning.