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∈Θ(logn/loglogn) 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.
Parallel priority queues based on binomial heaps
PINOTTI, Maria Cristina
2000
Abstract
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∈Θ(logn/loglogn) 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
