Найти журнал n наибольших записей за O (n) раз

Question

Есть ли способ найти журнал n наибольших элементов в массиве с n элементами за время O (n)?

Я бы создал массив на основе HeapPriorityQueue, потому что, если все элементы доступны, куча может быть создан за O (n) раз, используя конструкцию кучи снизу вверх. Тогда удаление первого элемента этой очереди приоритетов должно быть в O (1) раз, не так ли?

Answer 1

Тогда удаление первого элемента этой очереди с приоритетом должно быть в O (1) раз, не так ли?

Это будет O(logn), так как вы также удаляете первый элемент . Глядя на него без удаления - это O (1). Повторение этого удаления logn раз будет O(log^2(n)), которое все еще находится в O(n), поэтому это решение действительно будет соответствовать требованиям.

Другой вариант - использовать алгоритм выбора , чтобы непосредственно найти самый большой элемент log(n), который также будет O(n).

Answer 2

В основном да. Создание кучи занимает O (n), и это доминирует в алгоритме.

Удаление первого элемента может занять либо O (1), если куча не обновляет свои ключи после удаления, либо O (log n), если оно делает. В любом случае сложность удаления элементов log (n) из кучи с обновлением и без обновления будет O (log n * log n) и O (log n) соответственно. Оба они сублинейны.