Как вернуть первые N максимальных элементов из массива без сортировки массива?
Есть такой алгоритм. Называется quickSelect. Фактически, это обрезанный quickSort, где после выбора ведущего элемента и разбивки массива работа продолжается только в той половине, где находится раздел между первыми K элементами и остальными N-K.

Пусть у вас N элементов в массиве и надо вернуть K минимальных. Тогда сортировка будет работать за O(N log N), а quickselect за O(N) в среднем*. В худшем случае может быть и квадратичное время работы, но этот случай практически невозможен, если реализация испольует случайные числа для выбора ведущего элемента.

Если же вы боитесь этого худшего случая, или считаете себя самим невезучим человеком за всю историю человечества (или боитесь, что злой хакер взломает генератор случайных чисел и передаст вашей программе специально составленный массив, чтобы ее подвесить), то есть другой алгоритм, всегда работающий за O(n log k). При маленьких k - может быть даже быстрее первого алгоритма.

Суть его в том, чтобы в куче (heap aka priority queue) поддерживать пока найденные K минимальных элементов. При этом куча будет на максимум. Сначала туда кладутся первые k элементов массива, а потом каждый следующий вытесняет максимальный элемент в куче, если он его меньше.

* Вообще говоря, можно заставить quickselect и quicksort работать идеально всегда, если использовать алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна, который ищет медиану за O(n). Но на практике этот алгоритм не применятеся, потому что у него такая константа, что там на логарифм хватит и еще на квадрат останется.
Строго - никак.

Есть разные алгоритмы частичной сортировки с минимальной сложность O(N+KlogN), где K - количество максимумов, а N - размер массива, но совсем без сортировки не получится в общем случае.

Если не строго, то сильно зависит от специфики задачи, из которой нужно взять какие-то доп. условия и допущения. Именно они позволят оптимизировать алгоритм.

Например, если K не строгое, а лишь примерное, то можно прикинуть некий порог, выше которого эти элементы будут расположены. Скажем, K=10, N=1000 элементов, и в каждом случайное число от 1 до 1000. Тогда можно почти уверенно заявить, что все искомые элементы больше 970. Пробегаем массив один раз и находим все элементы больше 970. Их окажется около 30 плюс-минус. Главное, что не менее 10. Далее этот маленький массив можно отсортировать, но это снова сортировка.