Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10349116 | Journal of Systems and Software | 2005 | 8 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Networks and Communications
Authors
Andrej Brodnik, Svante Carlsson, Michael L. Fredman, Johan Karlsson, J. Ian Munro,