Вставки в максимальную кучу с максимум одним обменом

Question

Есть ли алгоритм для выполнения вставок в кучу с не более чем одним обменом (O(log n) сравнения разрешены)

Answer 1

Нет.

Рассмотрим эту кучу:

Предположим, вы добавили 200. Очевидно, что он должен стать новым корнем.

Так куда же деваться 100? Он не может стать ребенком 3-х лет, и это то, что он должен сделать, если у вас есть только один обмен.