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
Heaps with bits
Luleå University of Technology.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Quality Laboratories AB, IDEON Research Park, S-223 70, Lund.
1996 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 164, no 1-2, p. 1-12Article in journal (Refereed) Published
Abstract [en]

We show how to improve the complexity of heap operations and heapsort using extra bits. We first study the parallel complexity of implementing priority queue operations on a heap. The tradeoff between the number of extra bits used, the number of processors available, and the parallel time complexity is derived. While inserting a new element into a heap in parallel can be done as fast as parallel searching in a sorted list, we show how to delete the smallest element from a heap in constant time with a sublinear number of processors, and in sublogarithmic time with a sublogarithmic number of processors. The models of parallel computation used are the CREW PRAM and the CRCW PRAM. Our results improve those of previously known algorithms. Moreover, we study a variant, the fine heap, of the traditional heap structure. A fast algorithm for constructing this new data structure is designed using an interesting technique, which is also used to develop an improved heapsort algorithm. Our variation of heapsort is faster than I. Wegener's (1993) heapsort and requires less extra space.

Place, publisher, year, edition, pages
1996. Vol. 164, no 1-2, p. 1-12
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-5076DOI: 10.1016/0304-3975(95)00152-2ISI: A1996VJ09500001Local ID: 3178cc00-9c92-11db-8975-000ea68e967bOAI: oai:DiVA.org:ltu-5076DiVA, id: diva2:977950
Note
Godkänd; 1996; 20070105 (pafi)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-07-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Chen, Jingsen

Search in DiVA

By author/editor
Chen, Jingsen
By organisation
Computer Science
In the same journal
Theoretical Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 26 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