Рубрики

Алгоритмы | Сортировка | Вопрос 9

Предположим, мы сортируем массив из восьми целых чисел, используя heapsort, и мы только что завершили некоторые операции heapify (maxheapify или minheapify). Массив теперь выглядит так:
16 14 15 10 12 27 28
Сколько операций heapify было выполнено с корнем кучи?
(А) 1
(Б) 2
(С) 3 или 4
(D) 5 или 6

Ответ: (Б)
Объяснение: В Heapsort мы сначала строим кучу, затем выполняем следующие операции, пока размер кучи не станет равным 1.
а) Поменять корень с последним элементом
б) вызов heapify для root
в) уменьшить размер кучи на 1.

В этом вопросе дается, что heapify вызывался несколько раз, и мы видим, что два последних элемента в данном массиве — это 2 максимальных элемента в массиве. Таким образом, ситуация ясна, это maxheapify, который был вызван 2 раза.
Тест на этот вопрос

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

Алгоритмы | Сортировка | Вопрос 9

0.00 (0%) 0 votes