The weak-heap data structure: Variants and applications: Errata
Authors:Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Publication:Web document (2012)
Errata:
§ 2, Figure 7:
sift-down did not handle correctly the special case when the last node has only one child. The test "if kn return" was added. [The authors’ version and the source code corrected, 6 December 2012]
§ 3, Figure 9:
To cover all inserted nodes, the third line should be "rightn + k − 1" instead of "rightn + k − 2". [The authors’ version and the source code corrected, 10 November 2012]
§ 3, Figure 9:
For a large buffer, the interval of nodes to be considered was one too large. This change was only stylistic since the old version was correct, but it did some insignificant repetitive work. The initialization of left was changed to "max{n, ⌊right / 2⌋ + 1}". [The authors’ version and the source code corrected, 6 December 2012]
§ 3, Figure 9:
When there are only two nodes left, it is important to perform the last sift-down and sift-up operations in correct order. By performing the bottom-most sift-down first, then the top-most sift-down, then the top-most sift-up, and finally the bottom-most sift-up, we can avoid any unpleasant interference between the sift-down and sift-up operations. In particular, one should not execute the sift-down and sift-up operations in a mixed order as done in the original pseudo-code. [The authors’ version and the source code corrected, 6 December 2012]
§ 4.3, Figure 11:
In the figure on running times the unit of time is missing: y label " [ns]" added. [The authors’ version corrected, 1 October 2012]
Ref. 4:
3nd → 3rd
Related:<html.gif>HTML (Journal article)  <html.gif>HTML (Source code)  <html.gif>HTML (Source code)  
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 20.01.2013.