Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 517961.0, MPI für Informatik / Algorithms and Complexity Group
Comparator Networks for Binary Heap Construction
Authors:Brodal, Gerth Stølting; Pinotti, M. Cristina
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):1998
Title of Proceedings:Proceedings of the 6th Scandinavian Workshop on Algorithm Theory (SWAT-98)
Start Page:158
End Page:168
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Stockholm, Sweden
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
1998
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-E99AF9AE98C4B67CC125670200685D3A-...
ISBN:3-540-64682-5
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.