Title

Parallel Heap - An Optimal Parallel Priority Queue

Authors

Authors

N. Deo;S. Prasad

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

J. Supercomput.

Keywords

PARALLEL DATA STRUCTURE; HEAP; PRIORITY QUEUE; OPTIMAL PARALLEL; ALGORITHM; PARALLEL RANDOM ACCESS MACHINE; TREES; ALGORITHM; SEARCH; Computer Science, Hardware & Architecture; Computer Science, Theory &; Methods; Engineering, Electrical & Electronic

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 THETA(p) highest priority items and insertions of THETA(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.

Journal Title

Journal of Supercomputing

Volume

6

Issue/Number

1

Publication Date

1-1-1992

Document Type

Article

DOI Link

http://dx.doi.org/10.1007/bf00128644

Language

English

First Page

87

Last Page

98

WOS Identifier

WOS:A1992JR00500004

ISSN

0920-8542

Recommended Citation

"Parallel Heap - An Optimal Parallel Priority Queue" (1992). Faculty Bibliography 1990s. 440.
https://stars.library.ucf.edu/facultybib1990/440