Let we have a binary heap, realized by an array of length n. We write at the end of this array k elements. After that we want to restrore the heap property on this array of length n+k.
The complexity should be O(k + (logn)*log(log(n))).
My attemts. Of course we can restore the heap property of the full array with complexity O(n+k) using standart procedure. But it doesn't satisfy this complexity.
Also I have heard about the following method. Let we make a heap on the k last elements by O(k) and after that we create a "new heap" with first element greater (if we work with max-heaps) then the tops of first heap of size n and second heap of size k and with first heap as left subheap of new heap and second heap as right subheap. After that we delete top element by O(log(n+k)). But I really don't understand how to realize this approach, when we use an array representation.