Istituto di Scienza e Tecnologie dell'Informazione     
Brodal G., Pinotti M. C. Comparator networks for binary heap construction. In: Algorithm Theory - SWAT'98. 6th Scandinavian Workshop on Algorithm Theory (Stockholm, Sweden, July, 8-10 1998). Proceedings, pp. 158 - 168. S. Arnborg, L. Ivansson (Eds.) (eds.). (Lecture Notes in Computer Science, vol. 1432). Springer, 1998.
Comparator networks for constructing binary heaps of size n are presented which have size O(n log log n) and depth O(log n). A lower bound of n log log n - O(n) for the size of any heap construction network is also proven, implying that the networks presented are within a constant factor of optimal. We give a tight relation between the leading constants in the size of selection networks and in the size of heap construction networks.
Subject Data structures
C.3 special purpose and application based systems
E.1 Data Structures

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional