2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – greybeard Feb 27 '18 at 21:51
  • $\begingroup$ I do think the use of $n^2$ for one and $n$ for the other size unfortunate. $\endgroup$ – greybeard Feb 27 '18 at 21:53
  • $\begingroup$ 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? $\endgroup$ – D.W. Feb 27 '18 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.