Das S. K., Pinotti M. C. Parallel priority queues based on binomial heaps. In: Parallel Computing, vol. 26 (11) pp. 1411 - 1428. Elsevier Science Inc, 2000. |
Abstract (English) |
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. | |
Subject | Binomial heaps Carry adder Insert and delete operations Parallel data structures Meldable priority queues Time complexity E.1 Data Structures |
1) Download Document PDF |
Open access Restricted Private