В минимальной куче из n элементов с наименьшим элементом в root,

Question

В минимальной куче с n элементами с наименьшим элементом в root, 7-й наименьший элемент может быть найден во времени.

1. Θ (nlogn)
2. Θ (n)
3. Θ (logn)
4. Θ (1)

Мое понимание: время найти наименьший элемент в минимально-куче - один запрос операция - Θ (1) Время нахождения второго наименьшего элемента в минимальной куче - требует 2 ² -1 = 3 операции проверки, чтобы найти второй наименьший элемент из 3 элементов - Θ (1).

Время, чтобы найти 7-й наименьший элемент - требуется O (2 ⁷ -1) = O (127) проверочных операций, чтобы найти седьмой наименьший элемент из 127 возможных - Θ (1 ).

Короче говоря, если число требуемых операций не зависит от размера ввода n, то оно всегда равно Θ (1). (Здесь мы выполняем обход уровня кучи и проверяем элементы).

Или я тоже могу выглядеть так: если нам не разрешено обходить кучу и разрешены только операции кучи по умолчанию, мы будем ограничены выполнением Extract-min 7 раз, что будет O (n).

Я сомневаюсь, какой путь правильный, каким должен быть ответ.

Answer 1

Мин-куча - это конкретное c расположение узлов, которое вы можете пройти, чтобы найти 7-й наименьший элемент за время O (1), потому что вы должны посетить не более 127 узлов.

Очередь приоритетов - это абстрактный тип данных, который обеспечивает операцию извлечения-минимума, но которая не обязательно реализуется с минимальной кучей, которую вы могли бы пройти таким образом.

Answer 2

Извлечение мин в куче мин занимает log(n) время, а поскольку вы ограничиваете 7-ю позицию (константу), время, затраченное на это, по-прежнему порядка log(n).

Если вы пытаетесь найти 7-й наименьший элемент, один из способов сделать это - извлечь верхний элемент 6 раз из кучи и затем прочитать (не извлечь) верхнюю часть кучи. Это ваш 7-й самый маленький элемент. Ваше время выполнения по-прежнему составляет порядка log(n), поскольку вы удаляете постоянное количество раз из кучи. Теперь вы можете захотеть вставить 6 элементов обратно в кучу. У каждой вставки наихудшее время log(n), это все равно log(n), потому что 6 - это константа.