Parallel priority queues based on binomial heaps

We present an optimal parallel implementation of a meldable priority queue based on the binomial heap data structure. Our main result is an interesting application of the parallel computation of carry bits in a full adder logic to binomial heaps, thus optimizing the parallel time complexity of the Union (often called melding) of two queues. The Union operation as well as Insert, Min, Extract-Min and Multiple-Insert require doubly logarithmic time and are work-optimal, employing p epsilon Theta(log n/log log n) processors on the EREW-PRAM model. Parallel algorithms for Delete and Decrease-Key operations work by postponing the global effect of a node deletion/update, and achieve doubly logarithmic time and work-optimality in the amortized sense. (C) 2000 Elsevier Science B.V, All rights reserved.