Переключение с min-heap на max-heap без перестановки внутреннего массива

Question

Предположим, у нас есть min куча с некоторыми элементами, которые удовлетворяют свойству кучи.Что произойдет, если я изменю алгоритм с min heap на max heap без перестановки внутреннего массива?

То есть, если я оставлю массив без изменений, что произойдет, когда я добавлю элемент ввнутренний массив?

Answer 1

Рассмотрим следующий пример из Википедии :

Представление массива будет выглядеть так:

[1, 2, 3, 17, 19, 36, 7, 25, 100]

Теперь мы «меняем» кучу с минимального на максимальное, но без перестановки элементов и вставляем новый элемент «25». Позиция массива будет равна 9, поэтому родительский узел равен «19» в позиции 4.

После вставки мы должны многократно сравнивать новый элемент с его родителем, чтобы убедиться, что свойство heap (теперь max-heap => parent должен быть больше, чем child). Таким образом, мы должны поменять местами «25» с «19», «2» и «1», пока это не будет корневой узел.

Теперь свойство max-heap сохраняется для корневого узла (его дочерние элементы действительно меньше), но не для других узлов, например «3» по-прежнему является родителем «7» и нарушает условие максимальной кучи.

В заключение: выполнение того, что вы описываете, не меняет минимальную кучу на максимальную кучу.

Answer 2

Ты бы просто привинтил кучу.

Вы должны заново перенести груду (это можно сделать за время O (N)).