Parallel Heap - An Optimal Parallel Priority Queue

    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

    Language

    English

    First Page

    87

    Last Page

    98

    WOS Identifier

    WOS:A1992JR00500004

    ISSN

    0920-8542

    Share

    COinS