Мне задали вопрос, чтобы найти верхние элементы журнала (n) в несортированном массиве. Я знаю, что могу сделать это за время O(n) с помощью алгоритма выбора, чтобы найти log(n)-й по величине элемент, а затем найти все элементы, превышающие его. Однако можно ли использовать кучу или другую очередь с приоритетом, чтобы сделать это также за время O(n)?
Спасибо
Чтобы получить первые k элементов из несортированного списка, вы используете алгоритм Quickselect для разделения списка. такой массив, что первые k элементов находятся в начале массива.
Быстрый выбор в среднем составляет O(n). Однако в патологических случаях это может занять время O(n^2).
Используя кучу, выбор верхних k элементов из списка n составляет O (n log k). Если вы берете первые элементы журнала (n), то k = log(n), и ваша сложность равна O (n log (log (n)).
С точки зрения производительности использование кучи для выбора верхних элементов журнала (n) из списка почти наверняка будет быстрее, чем использование быстрого выбора. Причина в том, что Quickselect, несмотря на то, что он (в среднем) линейный, имеет высокую константу. Выбор первых 10 элементов из списка в 1 000 000 занимает почти столько же времени, сколько и выбор первых 100 000 элементов. Но моё исследование показывает, что использование кучи для сделать выбор быстрее, чем быстрый выбор, когда число для выбора намного меньше (менее 1%) от общего количества элементов. Учитывая, что основание журнала 2 из 1 000 000 равно примерно 20, почти наверняка алгоритм выбора кучи будет быстрее, чем Quickselect.
