tag

#top-k

5 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
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Streaming Top K

Streaming Top K Streaming Top K maintains the largest $k$ elements of a data stream. The input does not need to fit in memory, and the algorithm can update the answer after each new value. The standard method keeps a min heap of size $k$. The smallest value in the heap is the current cutoff for membership in the top $k$. Problem Given a stream of values $$ x_1, x_2,...
algorithms selection streaming top-k heap
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Top K by Quickselect

Top K by Quickselect Top K by Quickselect finds the $k$ largest elements by partitioning the array so that the top $k$ elements occupy one side. It uses the same idea as Quickselect, but returns a set instead of a single element. This method is faster than heap-based approaches when the data is in memory and only a single pass with partitioning is needed. Problem Given an array $A$ of...
algorithms selection top-k quickselect
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Top K Sort

Top K Sort Top K sort finds the ( k ) smallest or largest elements and returns them in sorted order. Unlike full sorting, it avoids ordering the entire dataset. You use it when only the best ( k ) items matter, such as ranking, search results, or recommendation systems. Problem Given an array ( A ) of size ( n ) and integer ( k ), compute: the smallest...
algorithms sorting top-k selection
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Top K by Heap

Top K by Heap Top K by Heap finds the largest or smallest $k$ elements without sorting the whole input. It keeps a heap of size $k$ and discards values that cannot belong to the final answer. For the $k$ largest elements, use a min heap. The heap root is the smallest value among the current candidates. When a new value is larger than the root, replace the root. Problem...
algorithms selection top-k heap