| Errata: | - § 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.
|
HTML (Conference paper)