Title

Parallel Heap: An Optimal Parallel Priority Queue

Keywords

heap; optimal parallel algorithm; Parallel data structure; parallel random access machine; priority queue

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. © 1992 Kluwer Academic Publishers.

Publication Date

3-1-1992

Publication Title

The Journal of Supercomputing

Volume

6

Issue

1

Number of Pages

87-98

Document Type

Article

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/BF00128644

Socpus ID

0037537068 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0037537068

This document is currently not available here.

Share

COinS