Navigation piles with applications to sorting, priority queues, and priority deques: Errata
Authors:Jyrki Katajainen and Fabio Vitale
Publication:Web document (2013)
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 jfirst_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.gif>HTML (Journal article)  
This page was generated by Jyrki Katajainen <> on 05.02.2013.