A simpler implementation and analysis of Chazelle's soft heaps
Haim Y. Kaplan, Uri Zwick · 2009
Chazelle (JACM 47(6), 2000) devised an approximate meldable priority queue data structure, called Soft Heaps, and used it to obtain the fastest known deterministic comparison-based algorithm for computing minimum spanning trees, as well as some new algorithms for selection and approximate sorting problems. If n elements are inserted into a collection of soft heaps, then up to εn of the elements still contained in these heaps, for a given error parameter ε, maybecorrupted, i.e., have their keys artificially increased. In exchange for allowing these corruptions, each soft heap operation is performed in O(log 1 ε) amortized time. Chazelle’s soft heaps are derived from the binomial heaps data structure in which each priority queue is composed of a collection of binomial trees. We describe a simpler and more direct implementation of soft heaps in which each priority queue is composed of a collection of standard binary trees. Our implementation has the advantage that no clean-up operations similar to the ones used in Chazelle’s implementation are required. We also present a concise and unified potential-based amortized analysis of the new implementation. 1