Title

Parallel Min-Max-Pair Heap

Abstract

Priority deques allow, in addition to the priority-queue operations of inserting an element and deleting the largest element, the deletion of the smallest element. Data structures like min-max heap, deap, min-max-pair heap, and interval heap, described in the literature, for implementing priority deques achieve only O(log n)-parallelism, where n is the number of elements. To alleviate this bottleneck, we present the parallel min-max-pair heap, a new parallel data structure for priority deques, which achieves a p-fold parallelism with p processors for all p≤n. First, we describe how it supports deletion of p largest elements, deletion of p smallest elements, and insertion of p elements in O(log n log p) time using p processors on the exclusive-read exclusive-write (EREW) parallel random-access machine (PRAM). Then, to obtain cost-optimal parallel algorithms, we show that the operations can be pipelined on this structure and that p operations can be handled in O(log n) time with p processors.

Publication Date

1-1-1994

Publication Title

Conference Proceedings - International Phoenix Conference on Computers and Communications

Number of Pages

322-328

Document Type

Article; Proceedings Paper

Identifier

scopus

Personal Identifier

scopus

Socpus ID

0028016840 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS