An algorithm to efficiently insert a list of elements into a binary heap (“bulk insertion”)

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).

• 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. – greybeard Mar 3 '19 at 21:34
• @greybeard, in my eye this is not elegant. I wonder for what proportion of the Earth's population it is. – Alexey Mar 3 '19 at 21:59
• (I wonder what the this in in my eye this is not elegant is referring to.) – greybeard Mar 3 '19 at 22:03
• @greybeard: your "brute force" solution. – Alexey Mar 3 '19 at 22:06

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)$$.

• 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 [...]" – Alexey Mar 3 '19 at 21:56
• 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? – Yuval Filmus Mar 3 '19 at 21:59

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

• 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. – greybeard Mar 5 '19 at 9:49