Merging and splitting priority queues and deques in parallel
1992 (English)In: Theory of Computing and Systems: ISTCS '92, Israel Symposium Haifa, Israel, May 27-28, 1992 Proceedings, Encyclopedia of Global Archaeology/Springer Verlag, 1992, 1-11 p.Conference paper (Refereed)
We investigate the parallel complexity of merging priority queues and double-ended priority queues (priority deques, for short). The implicit data structures that implement the queues studied in this paper are the heap, the twin-heap, the min-max heap, and the deap. It is known that heaps can be merged sequentially in sublinear time whereas merging min-max heaps requires linear sequential time. In this paper, we design efficient O(log n)-time parallel algorithms to merge two priority queue or deque structures of the same type on n and k elements (n≥k), respectively, which achieves the optimal speed-up. More precisely, two heaps of sizes n and k can be merged in O(log n) time with log k processors. Moreover, a related problem of splitting a heap on n elements into two heaps of sizes k and n-k is solved in O(log n) parallel time with log n processors, which also achieves the optimal speed-up. For the merge operation on priority deques, we show that the problem of merging twin-heaps can be solved in the same complexity as that for heaps both sequential and in parallel. Algorithms for merging two min-max heaps or two deaps of sizes n and k are demonstrated, which achieves a parallel time of O(log n) with k/log n+log k processors. The study of parallel solution to the problem of merging deaps also provides us with the first serial deap merging algorithm of time complexity O(k+log n·log k). The parallel computation model used in this paper is the EREW PRAM (Exclusive-Read Exclusive-Write Parallel Random Access Machine).
Place, publisher, year, edition, pages
Encyclopedia of Global Archaeology/Springer Verlag, 1992. 1-11 p.
Lecture Notes in Computer Science, ISSN 0302-9743 ; 601
IdentifiersURN: urn:nbn:se:ltu:diva-38711DOI: 10.1007/BFb0035161Local ID: d2f60280-a7fb-11dc-9534-000ea68e967bISBN: 978-3-540-55553-7 (print)OAI: oai:DiVA.org:ltu-38711DiVA: diva2:1012212
Israel Symposium on the Theory of Computing and Systems, ISTCS '92 : 27/05/1992 - 28/05/1992
Upprättat; 1992; 20071211 (ysko)2016-10-032016-10-03Bibliographically approved