ISSN:
1573-0484
Keywords:
Parallel data structure
;
heap
;
priority queue
;
optimal parallel algorithm
;
parallel random access machine
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such data structure to efficiently implement a truly parallel priority queue based on a heap structure. Employing p processors, the parallel heap allows deletions of θ(p) highest priority items and insertions of θ(p) new items, each in O(log n) time, where n is the size of the parallel heap. Furthermore, it can efficiently utilize processors in the range 1 through n.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00128644
Permalink