Aarhus University Seal

A Parallel Priority Queue with Constant Time Operations

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
We present a parallel priority queue that supports the following operations in constant time:parallel insertionof a sequence of elements ordered according to key,parallel decrease keyfor a sequence of elements ordered according to key,deletion of the minimum key element, anddeletion of an arbitrary element. Our data structure is the first to support multi-insertion and multi-decrease key in constant time. The priority queue can be implemented on the EREW PRAM and can perform any sequence ofnoperations inO(n) time andO(mlogn) work,mbeing the total number of keyes inserted and/or updated. A main application is a parallel implementation of Dijkstra's algorithm for the single-source shortest path problem, which runs inO(n) time andO(mlogn) work on a CREW PRAM on graphs withnvertices andmedges. This is a logarithmic factor improvement in the running time compared with previous approaches.
Original languageEnglish
JournalJournal of Parallel and Distributed Computing
Pages (from-to)4-21
Number of pages18
Publication statusPublished - 1998

Bibliographical note

Special issue on Parallel Data Structures

See relations at Aarhus University Citationformats

ID: 34705954