- § 1, fat heaps, # element comparisons performed by
- The bound 4 log3 n + O(1) ≈ 2.53 lg n is valid
when decrease is supported at the worst-case cost of O(lg n).
The correct bound is 5 log3 n + O(1) ≈ 3.16 lg n when
decrease is to be supported at the worst-case cost of O(1). [This
mistake was observed by Amr Elmasry when we wrote the paper "Fat heaps
without regular counters", 4 April 2011]