The complexity of heaps

ABSTRACT

In this paper, we investigate the complexity of heaps. In particular, we study the construction problem and the search problem for heaps. We derive an adversary-based lower bound for the heap construction problem. It is shown that 1.5(n + 1)–log(n + 1)–2 comparisons are necessary to construct a heap of size n in the worst case. This is the first non-trivial adversary lower bound for this problem, which improves the previous best lower bound based on an information theoretical argument for the heap construction. Furthermore, we prove fairly trivial tight upper and lower bounds on the number of comparisons needed to search for a given element in a heap. An optimal 3/4n-time search algorithm is presented. Our lower bound for searching is also demonstrated by an adversary argument, which improves the information theory bound for the problem as well.

REFERENCES

• 1: M. Aigner: Producing posets. Discrete Mathematics 35 (1981), 1-15.
• 2: M. J. Atallah and S. R. Kosaraju' An adversary-based lower bound for sorting. Information Processing Letters 13 (1981), 55- 57.
• 3: M. D. Atkinson: The complexity of orders. Proceedings of the NATO Advanced Study Institute on Algorithms and Orders (1987), 195-230.
• 4: S W Bent , J W John, Finding the median requires 2n comparisons, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.213-216, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22169]
• 5: B. Bollob~s and I. Simon: Repeated random insertion into a priority queue. Journal of Algorithms 6 (1985), 466~477.
• 6: Svante Carlsson, Average-case results on heapsort, BIT, v.27 n.1, p.2-17, 1987 [doi>10.1007/BF01937350]
• 7: S. Carlsson and J. Chen: A new lower bound for heap construction. Technical Report LU- CS-TR:90-67, Department of Computer Science, Lund University, 1990.
• 8: J. Chen, S. Carlsson and Th. Strothotte: Bounds for Producing Partial Orders. Proceedings of the International Conference for Young Computer Scientists (1991), 275-279.
• 9: Ernst E. Doberkat, An average case analysis of Floyd's algorithm to construct heaps, Information and Control, v.61 n.2, p.114-131, May 1984 [doi>10.1016/S0019-9958(84)80053-4]
• 10: Robert W. Floyd, Algorithm 245: Treesort, Communications of the ACM, v.7 n.12, p.701, Dec. 1964 [doi>10.1145/355588.365103]
• 11: G. N. Frederickson, The information theory bound is tight for selection in a heap, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.26-33, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100220]
• 12: Gaston H Gonnet , J Ian Munro, Heaps on heaps, SIAM Journal on Computing, v.15 n.4, p.964-971, Nov. 1986 [doi>10.1137/0215068]
• 13: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 14: C. J. McDiarmid , B. A. Reed, Building heaps fast, Journal of Algorithms, v.10 n.3, p.352-365, September 1989 [doi>10.1016/0196-6774(89)90033-3]
• 15: Hartmut Noltemeier, On a Generalization of Heaps, Proceedings of the International Workshop on Graphtheoretic Concepts in Computer Science, p.127-136, June 15-18, 1980
• 16: A. Sch5nhage: The production of partial orders. Astdrisque 38-39 (1976), 229-246.
• 17: A. Sch5nhage, M. Paterson and N. Pippenger: Finding the median. Journal of Computer and System Sciences 13 (1976), 184-199.
• 18: J. W. J. Williams: Algorithm 232: Heapsort. Communications of the ACM 7 (1964), 347- 348.
• 19: Andrew Chi-Chih Yao, On the complexity of partial order productions, SIAM Journal on Computing, v.18 n.4, p.679-689, Aug. 1989 [doi>10.1137/0218047]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

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

General Terms:
Algorithms, Theory, Verification