Optimal parallel initialization algorithms for a class of priorityqueues |
| |
Authors: | Olariu S Wen Z |
| |
Affiliation: | Dept. of Comput. Sci., Old Dominion Univ., Norfolk, VA; |
| |
Abstract: | An adaptive parallel algorithm for inducing a priority queue structure on an n-element array is presented. The algorithm is extended to provide optimal parallel construction algorithms for three other heap-like structures useful in implementing double-ended priority queues, namely min-max heaps, deeps, and min-max-pair heaps. It is shown that an n-element array can be made into a heap, a deap, a min-max heap, or a min-max-pair heap in O(log n+(n /p)) time using no more than n/log n processors, in the exclusive-read-exclusive-write parallel random-access machine model |
| |
Keywords: | |
|
|