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?


  • $\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, 2018 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, 2018 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, 2018 at 22:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.