Parallel complexity of heaps and min-max heaps
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)
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.
Lecture Notes in Computer Science, ISSN 0302-9743 ; 583
Research subject Dependable Communication and Computation Systems
IdentifiersURN: 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
Latin American Symposium on Theoretical Informatics : 06/04/1992 - 10/04/1992
Godkänd; 1992; 20070110 (ysko)2016-10-032016-10-03Bibliographically approved