You could: a) Heapify the list and ask for the first k numbers: O(k logn). b) Find the k-th statistic X and then iterate through the list adding only the numbers less than X: O(n) (difficult) or expected O(n) (it's just a tweaking of quicksort)