×

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

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25 Analysis of algorithms and problem complexity
68P05 Data structures