tag

#heaps

4 pages tagged

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.12 Top k Selection

6.12 Top k Selection Top k selection finds the largest or smallest k elements without necessarily sorting the entire input. It is closely related to partial sorting, but the emphasis is selection rather than presentation. The caller may only need the set of best candidates, not their complete internal order. Problem You have an array A[0..n-1] and an integer k . You want the largest k elements, or the smallest...
algorithms sorting selection top-k heaps May 4, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.6 Heap Sort

6.6 Heap Sort Heap sort derives order from a heap structure. It first builds a max-heap from the input array, then repeatedly extracts the maximum element and places it at the end of the array. The array itself stores the heap, so the algorithm runs in place. Problem You have an array A[0..n-1] . You want a sorting algorithm with guaranteed $O(n \log n)$ time, constant extra space, and no...
algorithms sorting heap-sort heaps May 4, 2026
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Rolling Median Sort

Rolling Median Sort Rolling median sort maintains the median value over a sliding window. Instead of fully sorting the window, it keeps just enough structure to extract the median efficiently. You use it when median or percentile queries are needed over recent data. Problem Given a stream ( x_1, x_2, \dots ) and window size ( w ), compute the median of: [ [x_{t-w+1}, \dots, x_t] ] after each step....
algorithms sorting median sliding-window heaps
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Median Maintenance

Median Maintenance by Two Heaps Median Maintenance keeps track of the median as values arrive one by one. It uses two heaps to maintain a balanced partition of the data. A max heap stores the lower half A min heap stores the upper half The median is derived from the roots of these heaps. Problem Given a stream $$ x_1, x_2, \dots, x_n $$ after each insertion, report the median...
algorithms streaming median heaps