scientific article; zbMATH DE number 4047086

From MaRDI portal
Publication:3783549





[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 \textit{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}\).\}











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3783549)