Two constant-factor-optimal realizations of adaptive heapsort: Errata
Author:Jyrki Katajainen
Publication:Web document (2012)
§ 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.

Related:<html.gif>HTML (Conference paper)  <html.gif>HTML (Journal article)  <html.gif>HTML (Source code)  
This page was generated by Jyrki Katajainen <> on 22.08.2012.