Istituto di Scienza e Tecnologie dell'Informazione     
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.
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

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional