Как мы можем избежать использования дополнительной работы в алгоритме сортировки кучи для поиска второго по величине элемента в массиве?

Question

Пожалуйста, дайте мне знать, сколько времени мы можем улучшить.

Answer 1

Если составить турнирную сетку (предположим, что число команд является степенью двойки) и предположить, что лучшая команда всегда побьет младшую, то лучшая команда будет играть против (и побеждать) команд lgN; вторая лучшая команда всегда будет одной из тех. Обратите внимание, что для поиска команды, занявшей второе место, всегда требуются сравнения lgN-1, но если кто-то хочет улучшить среднюю производительность поиска команды, занявшей третье место, пусть две первые команды, побитые лучшей командой, сыграют друг с другом, победитель получит из этой игры третья команда и т. д.

Третьей лучшей командой будет та, которая была побита второй лучшей командой (до или после того, как вторая лучшая команда была избита лучшей). Там будет либо lgN, либо lgN-1 (скорее всего, первый), поэтому сравнений lgN-1 будет достаточно, чтобы найти третью лучшую команду.

Answer 2

Если требуются только вторые по величине значения, то будет ли однопроходная сортировка пузырьков быстрее? По линиям:

biggest = array[0]

foreach element in array
  if element > biggest
    second_biggest = biggest
    biggest = element
  endif
next

что, если я правильно понял, это O (n).

Но эстергоны заявляют о (logn).

Однако каждое значение должно быть проверено хотя бы один раз, и это все, что сделано выше, поэтому я не вижу, как O (logn) быстрее / работает меньше в этом случае.

Answer 3

Если самый большой элемент находится в массиве [0], не является ли второй по величине в массиве [1] или массиве [2]? Поскольку каждый узел больше или равен двум своим сыновьям (и по транзитивности больше или равен всем его потомкам).

Answer 4

Сортировка кучи занимает O(n Logn) время для сортировки кучи длины n.Чтобы получить второй по величине элемент, вы должны использовать heapify дважды.Второй номер - это то, что вы ищете.это займет 2 * logn (куча) времени.Сложность O(logn).