Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Parallel heap construction using multiple selection
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
1994 (English)In: Parallel Processing: CONPAR 94 - VAPP VI Third Joint International Conference on Vector and Parallel Processing Linz, Austria, September 6-8, 1994 Proceedings / [ed] Bruno Buchberger, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1994, p. 371-380Conference paper, Published paper (Refereed)
Abstract [en]

We consider the problem of constructing data structures that implement priority queues (viz. the heap) and double-ended priority queues (namely, the twin-heap, the min-max heap, and the deap) quickly and optimally in parallel. Whereas all these heap-like structures can be built in linear sequential time, we show in this paper that the construction problem can be solved in O(log n·log* n/log log n) time using n·log log n/log n·log * n processors in the Arbitrary CRCW PRAM model. Moreover, by applying random sampling techniques, we reduce the construction time to O with probability ≥ 1-n-c for some constant c>0. As a by-product, we also investigate the parallel complexity of the multiple selection problem. The problem is to select a subset of elements having specified ranks from a given set. We design optimal solutions to the problem with respect to various models of parallel computation.

Place, publisher, year, edition, pages
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1994. p. 371-380
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 854
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-32231DOI: 10.1007/3-540-58430-7_33Local ID: 6a862cc0-a4e0-11dc-8fee-000ea68e967bISBN: 978-3-540-58430-8 (print)OAI: oai:DiVA.org:ltu-32231DiVA, id: diva2:1005465
Conference
Joint International Conference on Vector and Parallel Processing : 06/09/1994 - 08/09/1994
Note
Godkänd; 1994; 20071207 (ysko)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-01-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Chen, Jingsen
By organisation
Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 19 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf