Parallel Algorithms for Priority Queue Operations

Using EREW-PRAM algorithms on a tournament based complete binary tree we implement the insert and extract-min operations with p = log N processors at costs O(1) and O(loglog N) respectively. Previous solutions [4, 7] under the PRAM model and identical assumptions attain O(log log N) cost for both operations. We also improve on constant factors the asymptotic bound for extract-min since in it we reduce the use of communication demanding primitives. The tournament tree enables the design of parallel algorithms that are noticeably simple.