Получите k-самых больших элементов из массива с n элементами, где n намного больше, чем k

Question

Предположим, у вас есть несортированный массив длины n. Теперь вы хотите взять k-самые большие элементы из массива. Мы также знаем, что n намного больше, чем k.

Моя наивная идея - отсортировать массив и вывести k-самых больших элементов. Это будет стоить O (nlog (n)). Есть ли более эффективный алгоритм, который использует тот факт, что n намного больше, чем k?

Answer 1

Да, более эффективные алгоритмы существуют.

Получить k первых элементов, построить min - кучу, содержащую эти k элементов.

Пройдите через другие элементы. Если текущий элемент больше кучи, удалите верх и вставьте текущий элемент.

После конца куча будет содержать k самых больших элементов.

Сложность O(N*logK)

---

Также рассмотрим алгоритм QuickSelect со средним временем O (n) (в то время как он имеет наихудший случай вплоть до квадратичного)