An algorithm for merging heaps

DOI10.1007/BF00264229MaRDI QIDQ797280zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Thomas Strothotte, Jörg-Rüdiger Sack

Publication date 1985

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00264229

zbMATH Keywords

heapsmergingpriority queues

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25)

Review text

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

Recommendations

• Merging heaps in parallel
• A Note on HEAPSORT
• scientific article; zbMATH DE number 4014031
• A characterization of heaps and its applications
• Range-restricted mergeable priority queues

Cited in

(9)

• A pointer-free data structure for merging heaps and min-max heaps
• A tree-based mergesort
• The heap-mergesort
• Efficient privacy-preserving data merging and skyline computation over multi-source encrypted data
• A survey on priority queues
• Merging heaps in parallel
• The K-D heap: An efficient multi-dimensional priority queue
• Range-restricted mergeable priority queues
• A characterization of heaps and its applications

This page was built for publication: An algorithm for merging heaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q797280)