| Errata: | - § 3, Bulk insertion for weak heaps:
-
For the bulk-insertion 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 constant-time
bulk-insertion 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.
|
HTML (Conference paper)