An algorithm for merging meaps |
| |
Authors: | Jörg -R Sack Thomas Strothotte |
| |
Affiliation: | (1) School of Computer Science, Carleton University, K1S 5B6 Ottawa, Ont., Canada;(2) INRIA Rocquencourt, B.P. 105, F-78153 Le Chesnay, France |
| |
Abstract: | Summary We present an algorithm to merge priority queues organized as heaps. The worst case number of comparisons required to merge two heaps of sizes k and n is O(log(n)*log(k)). The algorithm requires O(k) +log(n)*log (k)) data movements if heaps are implemented using arrays and O(log(n)*log(k)) for a pointer-based implementation. Previous algorithms require either O(n+k) data movements and comparisons, or O(k*log(log(n+k))) comparisons and O(k*log(n+k)) data movements. The algorithm presented in this paper improves on the previous algorithms for the case when k>log(n).This work was done while the authors were at McGill University, Montréal, Canada |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|