restoring heap property after insertion several elements

2003 views arrays

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.

answered question

1 Answer


The simplest thing would be to apply the "heap insert" operation on each of the k new elements, starting with the first. This has complexity O(k * log(n)), which is good if k is much smaller than n.

posted this

Have an answer?


Please login first before posting an answer.