de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Comparator Networks for Binary Heap Construction

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44187

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Brodal, G. S., & Pinotti, M. C. (1998). Comparator Networks for Binary Heap Construction. In S. Arnborg, & L. Ivansson (Eds.), Proceedings of the 6th Scandinavian Workshop on Algorithm Theory (SWAT-98) (pp. 158-168). Berlin, Germany: Springer.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-3773-B
Abstract
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.