We explore two ways of incorporating parallelism into priority queues. The first is to speed up the execution of individual priority operations so that they can be performed one operation per time step, unlike sequential implementations which require O(log N) time steps per operation for an N element heap. We give an optimal parallel implementation that uses a linear array of O(log N) processors. Second, we consider parallel operations on the priority queue. We show that using a d-dimensional array (constant d) of P processors we can insert or delete the smallest P elements from a heap in time O(P/sup 1/d/log/sup 1-1/d/ P), where the number of elements in the heap is assumed to be polynomial in P. We also show a matching lower bound, based on communication complexity arguments, for a range of deterministic implementations. Finally, using randomization, we show that the time can be reduced to the optimal O(P/sup 1/d/) time with high probability.
展开▼
机译：我们探讨了将并行性纳入优先级队列的两种方式。首先是加速各个优先级操作的执行，使得每个时间步骤可以执行一个操作，与需要为n个元素堆的每个操作的O（log n）时间步骤的顺序实现。我们提供了一种最佳的并行实现，它使用O（log n）处理器的线性阵列。其次，我们考虑在优先级队列上的并行操作。我们表明，使用P处理器的D维数组（常数d），我们可以从堆中插入或删除最小的p元素O（p / sup 1 / d / log / sup 1-1 / d / p） ，其中假设堆中的元素数量在P中是多项式。我们还示出了基于通信复杂性参数的匹配下限，用于一系列确定性实现。最后，使用随机化，我们表明时间可以减少到具有高概率的最佳O（P / SUP 1 / D /）时间。
展开▼
