4
$\begingroup$

I wonder if there is any elegant algorithm for inserting a list of elements into a binary heap (at once) whose performance would be close to that of inserting elements one by one when there are only a few elements to insert, and which would still run in linear time in the worst case (when there is a lot of elements to insert).

$\endgroup$
  • $\begingroup$ Assume n to be the number of new elements, m the size of the heap "before". Brute force: fix a limit below which to insert one by one ($O(\log m)$ with a self-respecting heap implementation), build afresh above ($O(m+n)$). With a fast merge for heaps (not given for binary heaps as per English wikipedia), there may be a region where turning the new elements into a heap ($O(n)$) and merging beats rebuilding. Elegance lies in the eye of the beholder. $\endgroup$ – greybeard Mar 3 at 21:34
  • $\begingroup$ @greybeard, in my eye this is not elegant. I wonder for what proportion of the Earth's population it is. $\endgroup$ – Alexey Mar 3 at 21:59
  • $\begingroup$ (I wonder what the this in in my eye this is not elegant is referring to.) $\endgroup$ – greybeard Mar 3 at 22:03
  • $\begingroup$ @greybeard: your "brute force" solution. $\endgroup$ – Alexey Mar 3 at 22:06
3
$\begingroup$

Wikipedia describes a procedure, due to Floyd, which constructs a heap from an array in linear time.

It also mentions a procedure for merging two heaps, of sizes $n$ and $k$, in time $O(k + \log k \log n)$.

Altogether, we can add $k$ elements to a heap of length $n$ in time $O(k + \log k \log n)$: first build a heap containing $k$ elements to be inserted (takes $O(k)$ time), then merge that with the heap of size $n$ (takes $O(k+ \log k \log n)$ time).

Compare this to repeated insertion, which would run in time $O(k\log n)$.

$\endgroup$
  • $\begingroup$ My question is about inserting elements into an existing heap. It can happen that there is only 10 elements to insert into a heap of 10000 elements. "[...] whose performance would be close to that of inserting elements one by one when there are only a few elements to insert [...]" $\endgroup$ – Alexey Mar 3 at 21:56
  • $\begingroup$ Wikipedia mentions an algorithm for merging two heaps, of sizes $n$ and $k$, in time $O(\log n \log k)$. See here. Does this help you? $\endgroup$ – Yuval Filmus Mar 3 at 21:59
3
$\begingroup$

A citation without too much consideration or research:
heap bulk insert, Elmasry/Katajainen style (figure 3):

procedure: bulk-insert
input: $A[1..n_0+l]$: array; $n_0$: index; $l$: index
data structures: $A[1..n_0]$: partial heap; $A[n_0+ 1..n_0+l]$: buffer
$right$$n_0+l$
$left$$\max \{n_0+ 1, \lfloor (n_0 + l)/2 \rfloor\}$
while $right \ne 1$
   $left ← \lfloor left/2 \rfloor$
   $right ← \lfloor right/2 \rfloor$
   for $j \in \{right, right−1, \cdots, left\}$
      sift-down$(A, j, n_0+l$)

Elmasry, Amr; Katajainen, Jyrki: Towards ultimate binary heaps

$\endgroup$
  • $\begingroup$ Looks a straightforward adaption of (the better part of) Floyd's Treesort 3 (ACM Algorithm 245); as such, there may be prior art. Elegant in the eye of an old hand at coding. $\endgroup$ – greybeard Mar 5 at 9:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.