A simpler implementation and analysis of Chazelle's soft heaps

ABSTRACT

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 ε, may be corrupted, 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.

REFERENCES

• 1: M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448--461, 1973.
• 2: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 3: Bernard Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the ACM (JACM), v.47 n.6, p.1028-1047, Nov. 2000 [doi>10.1145/355541.355562]
• 4: Bernard Chazelle, The soft heap: an approximate priority queue with optimal error rate, Journal of the ACM (JACM), v.47 n.6, p.1012-1027, Nov. 2000 [doi>10.1145/355541.355554]
• 5: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 6: Dorit Dor , Uri Zwick, Selecting the Median, SIAM Journal on Computing, v.28 n.5, p.1722-1758, April/May 1999 [doi>10.1137/S0097539795288611]
• 7: Dorit Dor , Uri Zwick, Median Selection Requires $(2+\epsilon)n$ Comparisons, SIAM Journal on Discrete Mathematics, v.14 n.3, p.312-325, 2001 [doi>10.1137/S0895480199353895]
• 8: Seth Pettie , Vijaya Ramachandran, An optimal minimum spanning tree algorithm, Journal of the ACM (JACM), v.49 n.1, p.16-34, January 2002 [doi>10.1145/505241.505243]
• 9: Seth Pettie , Vijaya Ramachandran, Randomized minimum spanning tree algorithms using exponentially fewer random bits, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-27, March 2008 [doi>10.1145/1328911.1328916]
• 10: A. Schönhage, M. Paterson, and N. Pippenger. Finding the median. Journal of Computer and System Sciences, 13(2):184--199, 1976.
• 11: Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms