Errata:   § 3, Bulk insertion for weak heaps:

For the bulkinsertion procedure described in the text the amortized
cost per insert is Ω(lglg n), not O(1) as
claimed. The key to the detection of this error was an innocent
referee comment that the proof of the amortized time bound was
difficult to understand. Thank you! [Reported by Amr Elmasry, 28
March 2012]
Fortunately, this error was fixable. A correct constanttime
bulkinsertion procedure is described in the journal version of the
paper. Now the proof is also easier to understand. The error has also
been corrected in our source code. In spite of this disparency in
theory, the two versions behaved equally fast in practice.
