Two-tier relaxed heaps: Errata
Author:Jyrki Katajainen
Publication:Web document (2012)
§ 1, fat heaps, # element comparisons performed by delete:
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]
Related:<html.gif>HTML (Journal article)  
This page was generated by Jyrki Katajainen <> on 09.11.2012.