| 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 k ≥
n 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 "right ← n + k − 1" instead of
"right ← n + 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 (Journal article) HTML (Source code) HTML (Source code) |
This page was generated by
Jyrki Katajainen
<jyrki@di.ku.dk> on 20.01.2013.
|