de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Comparator networks for binary heap construction

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44187

Brodal,  Gerth Stølting
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

1998-1-002
(beliebiger Volltext), 10KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Brodal, G. S., & Pinotti, M. C.(1998). Comparator networks for binary heap construction (MPI-I-1998-1-002). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-9A0B-B
Zusammenfassung
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 constructiion networks.