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
Worst case constant time priority queue
Blekinge Institute of Technology, Karlskrona.
Department of Computer Science, Rutgers University, New Brunswick, NJ.
Luleå tekniska universitet.
Show others and affiliations
2005 (English)In: Journal of Systems and Software, ISSN 0164-1212, E-ISSN 1873-1228, Vol. 78, no 3, p. 249-156Article in journal (Refereed) Published
Abstract [en]

We present a new data structure of size 3M bits, where M is the size of the universe at hand, for realizing a discrete priority queue. When this data structure is used in combination with a new memory topology it executes all discrete priority queue operations in O(1) worst case time. In doing so we demonstrate how an unconventional, but practically implementable, memory architecture can be employed to sidestep known lower bounds and achieve constant time performance.

Place, publisher, year, edition, pages
2005. Vol. 78, no 3, p. 249-156
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-5480DOI: 10.1016/j.jss.2004.09.002ISI: 000232960100003Scopus ID: 2-s2.0-26444544209Local ID: 39820510-a0a2-11db-8975-000ea68e967bOAI: oai:DiVA.org:ltu-5480DiVA, id: diva2:978354
Note
Validerad; 2005; 20060922 (ysko)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 textScopus

Authority records BETA

Brodnik, Andrej

Search in DiVA

By author/editor
Brodnik, Andrej
In the same journal
Journal of Systems and Software
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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