2011-gre-cs-practice-book.pdf/Q02 — различия между версиями

Версия 20:04, 18 декабря 2024

• 2011-gre-cs-practice-book.pdf/Q02

Вопрос: Q02-08c765

Бинарная куча использует следующий массив a[] = [9, 7, 4, 2, 6, 1, 3] для хранения своих элементов. Какими будут оставшиеся значения элементов массива после одной операции удалить-максимум из кучи?

Ответы

• [7, 4, 2, 6, 1, 3]
• [7, 4, 6, 2, 1, 3]
• [7, 4, 6, 2, 3, 1]
• [7, 6, 4, 2, 1, 3]
• Правильный ответ: [7, 6, 4, 2, 3, 1]

Объяснение

Исходники — вопрос 2 на 14 странице книги «2011-gre-cs-practice-book.pdf»

По рисунку видно, что после удаления 9, на его место встанет последний элемент снизу, он же последний в массиве, то есть 3. И эта тройка опускается вниз по принципу «тот кто больше из двух потомков встанет на мое место». Сначала это 7 (7 > 4), затем 6 (6 > 2).