Пусть у нас есть двоичная куча, реализованная массивом длины n. Мы пишем в конце этого массива k элементов. После этого мы хотим восстановить свойство heap для этого массива длиной n + k.
Сложность должна быть O (k + (logn) * log (log (n))).
Мои заботы. Конечно, мы можем восстановить свойство кучи полного массива со сложностью O (n + k), используя стандартную процедуру. Но это не удовлетворяет этой сложности.
Также я слышал о следующем методе. Пусть мы создадим кучу из последних k элементов с помощью O (k) и после этого создадим «новую кучу» с первым элементом больше (если мы работаем с max-кучами), то вершины первой кучи размера n и второй кучи размером k и с первой кучей в качестве левой подпучки новой кучи и второй кучей в качестве правой подпучки. После этого мы удаляем верхний элемент с помощью O (log (n + k)). Но я действительно не понимаю, как реализовать этот подход, когда мы используем представление массива.