Small-Rank Selection in Parallel, with Applications to Heap Construction
✍ Scribed by Paul F Dietz; Rajeev Raman
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 115 KB
- Volume
- 30
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
We study the parallel complexity of selecting the kth smallest of n elements Ž on the CRCW PRAM. We show that this problem can be solved in O log log n q . Ž. log krlog log n time and O n operations for all 1 F k F nr2, which is superior to existing deterministic bounds when k is small compared to n. A matching time lower bound is shown for all algorithms that use n or fewer processors to solve this problem. As an application of the selection result, we give an algorithm for Ž . permuting n items in an array into heap order on a CRCW PRAM in O log log n Ž . time and O n operations. By using randomization, the running time of this Ž . algorithm can be improved to O log log log n with high probability, still perform-Ž . Ž . ing O n operations. No PRAM algorithm with o log n run time was previously known for this problem. We also obtain improved algorithms for constructing k-bandwidth heaps and min-path heaps.