| Navigation piles with applications to sorting, priority queues, and priority deques: Errata | | Authors: | Jyrki Katajainen and Fabio Vitale | | Publication: | Web document (2013) | | Errata: | - Section 2, function start_of_offset:
- As discussed
in the text, the value of bits_upto_this_level should be
set to ∑β=0δ − 12β(η − β) which is
(η − δ + 2)2δ − η − 2 in a closed form. [Reported
by Claus Jensen, 1 May 2006]
- Section 2, function push:
-
Function push_back increases n by one. This means that
for some branches above the last leaf the offsets are not yet set
correctly. Therefore, the binary search should not be applied for the whole
special path, but only its top part starting from the bottom-most
branch that has two children. This error can be corrected by replacing
the first two assignments in function
binary_search_on_special_path with the following:
node_index j ←
first_ancestor_with_more_more_than_one_child(last_leaf());
level Δ ← depth(j);
Here the function
first_ancestor_with_more_than_one_child is the
first part of function
first_two_ancestors_with_more_than_one_child.
[Reported by Claus Jensen, 1 May 2006]
| | Related: |  HTML (Journal article) |
This page was generated by
Jyrki Katajainen
<jyrki@di.ku.dk> on 05.02.2013.
|