Draws, Lars; Eriksson, Patrik; Forslund, Erik; Höglund, Leif; Vallner, Sören; Strothotte, Thomas Two new algorithms for constructing min-max heaps. (English) Zbl 0642.68057 Algorithm theory, Proc. 1st Scand. Workshop SWAT, Halmstad/Sweden 1988, Lect. Notes Comput. Sci. 318, 43-50 (1988). [For the entire collection see Zbl 0639.00043.] We study the computational complexity of constructing implicit, double- ended priority queues organized as min-max heaps, presenting two new algorithms for solving the problem. To construct a min-max heap on n elements, the first one uses 187/96 n\(=1.95... n\) comparisons in the worst case (neglecting lower. \(\lambda_ 1>0\) and \(\lambda_ 2,\lambda_ 3<0\). The Ricci condition then implies in addition that (2) \(\lambda_ 1\geq | \lambda_ k|\) for \(k=2,3\) and thus \(| A| \leq \sqrt{3}\lambda_ 1\). The condition inf \(\Lambda\) \({}^+=0\) now implies that \(\inf | A| =0\), as desired. (This analysis requires \(n=3\) because the analog of (1) does not hold if \(n\geq 4\), while the analog of (2) is false when \(n=2.)\) {Reviewer’s comment: A result of S. Chern [see Abh. Math. Semin. Univ. Hamb. 29, 77-91 (1965; Zbl 0147.209), especially Theorem 4] verifies the conjecture for all n provided M is an entire nonparametric hypersurface in \(R^{n+1}\).} Reviewer: R.C.Reilly Cited in 2 Documents MSC: 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems 68Q25 Analysis of algorithms and problem complexity 68P05 Data structures Keywords:double-ended priority queues; min-max heaps Citations:Zbl 0639.00043; Zbl 0147.209 PDFBibTeX XML