# Is there an efficient way to insert n items into an n^2 sized heap

I am aware of a O(n) algorithm for constructing a new heap of n items, this is better than repeatedly inserting into an empty heap which takes O(nlogn). I would like to know if there is something similar for inserting a group of n items into an existing heap. Rather than using repeated insertion, is there something more efficient?

Thanks

• Depends. You can build a heap of the additional items ($O(n)$) and merge them - ($O(\log^2{n})$) with standard binary heaps, faster with others, e.g. Fibonacci heaps (note the discrepancy to the claim attributed to Sack&Strothotte). – greybeard Feb 27 '18 at 21:51
• I do think the use of $n^2$ for one and $n$ for the other size unfortunate. – greybeard Feb 27 '18 at 21:53
• I don't understand your question. You say you know of an algorithm for "inserting n items into a heap", but you want an algorithm for "inserting a group of n items into a heap". What's the difference? What distinction are you trying to make? What exactly is the problem you are trying to solve? – D.W. Feb 27 '18 at 22:00