An algorithm for merging heaps (Q797280)

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)\).