complexityheapssorting
keep a heap small for top-k values
Anonymous
For the k smallest values, keep a max heap of size k; each new value can be compared with the largest retained value. This uses space proportional to k and about n log k heap work. When k is close to n, sorting the full input may be simpler.
0