Merge Two Heaps
What you'll learn: How to combine two separate heaps into a single heap while maintaining the heap property.
When you have two valid heaps and need to merge them into one, you face an interesting challenge: both structures satisfy the heap property independently, but combining them requires restoring that property for the unified structure.
The Naive Approach: O(n log n)
The simplest strategy treats one heap as your base and inserts each element from the second heap individually. Since you already know Insert takes O(log n) time and you're inserting m elements from the second heap:
- Start with heap A (size n)
- For each element in heap B (size m), call
Inserton heap A - Total time: O(m log(n+m))
This works but doesn't take advantage of the fact that both inputs are already heaps.
The Better Approach: Concatenate and Build
A more efficient strategy leverages the Build Heap operation you learned earlier:
- Combine both heap arrays into one large array (simple concatenation)
- Run Build Heap on the combined array
Since Build Heap runs in O(n) time and you have (n + m) total elements, this entire merge completes in O(n + m) time — much better than repeatedly inserting!
This approach is especially effective when merging heaps of similar sizes.
When Each Strategy Shines
- Naive insertion: Best when one heap is much smaller than the other (inserting 10 elements into a 10,000-element heap)
- Build Heap: Best when heaps are roughly similar in size or you need optimal worst-case performance
Key Takeaway: Merging heaps can be done naively in O(n log n) by repeated insertion, or optimally in O(n) by concatenating arrays and running Build Heap on the result.