Как ускорить поиск top-N без полной сортировки

Условие

Нужно выбрать N наибольших значений из потока M элементов, где N намного меньше M. Как избежать сортировки всего набора и какую сложность получить?

Ответ

Поддерживайте min-heap размера N. Корень хранит наименьший из текущих лучших; более крупный новый элемент заменяет его. Время O(M log N), память O(N).

Первые N элементов заполняют heap, затем каждый следующий сравнивается с корнем. Если нужен отсортированный результат, в конце отсортируйте только N выбранных значений. При N=0 сразу возвращайте пустой результат, при N>M — все элементы. Для массива существуют и алгоритмы отбора, но у потока heap удобнее из-за ограниченной памяти.