Fat heaps without regular counters: Errata
Author:Jyrki Katajainen
Publication:Web document (2012)
§ 2, Description of delete:
The bubbling-up procedure does not work since the deleted node can be marked. When it is replaced by its parent, not much is known about the relation between the replacement node and the nodes in the right subtree of the deleted node; at worst the heap order may be broken. [This mistake was communicated to us by Dan Larkin in another context, 10 August 2012]

One way to accomplish the deletion is to rely on the top-down procedure proposed by Vuillemin [Communications of the ACM 21(4) (1978), 309-315] for binomial queues. The error was corrected in this way in the journal version of the paper. Luckily, our actual implementation used the bottom-up borrow-based delete so this mistake did not have any effect on our experimental results.

Related:<html.gif>HTML (Conference paper)  <html.gif>HTML (Journal article)  <html.gif>HTML (Source code)  
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 12.05.2013.