PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Brodal G., Pinotti M. C. Comparator networks for binary heap construction. In: Theoretical Computer Science, vol. 250 (1/2) pp. 235 - 245. Elsevier Science Inc, 2000.
 
 
Abstract
(English)
Comparator networks for constructing binary heaps of size n are presented which have size O(nloglogn) and depth O(logn). A lower bound of nloglogn−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 Binary heaps
Comparator networks
Selection networks
Lower bounds
C.3 special purpose and application based systems


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