Change search
ReferencesLink to record
Permanent link

Direct link
Parallel complexity of heaps and min-max heaps
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Luleå tekniska universitet.
1992 (English)In: LATIN '92: 1st Latin American Symposium on Theoretical Informatics, São Paulo, Brazil, April 6 - 10, 1992 proceedings / [ed] Imre Simon, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1992, 108-116 p.Conference paper (Refereed)
Abstract [en]

We study parallel solutions to the problem of implementing priority queues and priority deques. It is known that data structures for the implementation (e.g., the heap, the minmax heap, and the deap) can be constructed in linear sequential time. In this paper, we design optimal Ω((log log n)2) time parallel algorithms with n/(log logn)2 processors for the constructions on the parallel comparison tree model. For building heaps in parallel, our algorithm improves the previous best result of Ω(log n) time with n/log n processors. For building min-max heaps and deaps, our algorithms are the first attempt to design parallel algorithms for constructing the data structures of the priority deque that are cost optimal.

Place, publisher, year, edition, pages
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1992. 108-116 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 583
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-37944DOI: 10.1007/BFb0023822Local ID: c26379b0-a0dc-11db-8975-000ea68e967bISBN: 3-540-55284-7OAI: oai:DiVA.org:ltu-37944DiVA: diva2:1011443
Conference
Latin American Symposium on Theoretical Informatics : 06/04/1992 - 10/04/1992
Note
Godkänd; 1992; 20070110 (ysko)Available from: 2016-10-03 Created: 2016-10-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Chen, Jingsen
By organisation
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 1 hits
ReferencesLink to record
Permanent link

Direct link