PUMA
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.
 
 
Abstract
(English)
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