Правильно ли я выполнил операцию извлечения max на этой max-куче?

Question

Я пытаюсь понять, как работают кучи.

У меня есть следующая куча:

Теперь я хочу извлечьмаксимальное значение.

Первое, что я делаю, это удаляю корень 42, затем помещаю последний элемент в кучу (6) в корневую позицию.Затем я выполняю max-heapify, чтобы найти правильное место для 6.

6, которое больше, чем у его двух детей, поэтому я поменяю его с самым большим ребенком 41, сделав 41 новым корнем.

6 теперь имеет детей 3 и 9, поэтому я снова поменяю их местами с большим ребенком 9

В итоге я получаю кучу

Правильно ли я выполнял extract-max?

Answer 1

Да! Извлечь max работает рекурсивно. Найти самый большой элемент среди трех, то есть родителя и двух их потомков. Если самый большой не родительский, то поменять местами самый большой элемент с родителем и вызвать извлечь максимум из наибольшего.