Parallel Heap Operations on an EREW PRAM |
| |
| Affiliation: | 1. Fondazione Bruno Kessler, via Sommarive 18, Povo I-38123, TN, Italy;2. University of Trento, Italy;1. School of Automation, University of Electronic Science and Technology of China, Chengdu 610054, P R China;2. Department of Geography and Anthropology, Louisiana State University, Baton Rouge, LA 70803, United States;1. College of Computer Science and Technology, Zhejiang University, China;2. School of Computer Science and Engineering, University of Electronic Science and Technology of China, China;1. DEI, University of Padua, viale Gradenigo 6, Padua, Italy;2. Computer Information Systems, Missouri State University, 901 S. National, Springfield, MO 65804, USA |
| |
| Abstract: | We consider parallel heap operations on the exclusive-read exclusive-write parallel random-access machine. We first present an O(n/p + log p) time parallel algorithm to construct a heap of n elements using p processors, which is optimal for p θ(n/log n). We then propose a parallel root deletion algorithm. In a preparatory step, a data structure for dynamic processor allocation is constructed using O((n/log n)1 − 1/k) processors in O(log k) time for some constant k, 1 ≤ k ≤ ⌈log(n/log n)⌉. A sequence of root deletions can then be performed, each of which takes O((log n)/p + log p + log log n) time using p processors. Finally, we discuss a parallel algorithm running in O((log n)/p + log p) time for inserting an element into a heap, which is optimal for p = θ((log n)/log log n). Both deletion and insertion algorithms run in O(log log n) time when p = θ((log n)/log log n). |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
