Рубрики

Структуры данных | Куча | Вопрос 11

Учитывая две максимальные кучи размера n каждая, какова минимальная возможная временная сложность, чтобы создать одну максимальную кучу размера из элементов двух максимальных куч?
(A) O (nLogn)
(B) O (nLogLogn)
(C) O (n)
(D) O (nLogn)

Ответ: (с)
Объяснение: Мы можем построить кучу из 2n элементов за O (n) времени. Ниже приведены шаги.

Создайте массив размером 2n и скопируйте элементы обеих куч в этот массив.

Вызов кучи сборки для массива размером 2n. Операция построения кучи занимает O (n) времени.
Тест на этот вопрос

Рекомендуемые посты:

Структуры данных | Куча | Вопрос 11

0.00 (0%) 0 votes