CODEWITHSUNDEEP
data-structuresbig-otime-complexitybinary-heap
user2766222
user2766222

Reputation: 9

Merging heap arrays with linear complexity

how can I merge two heap arrays into one balanced heap array and still maintain linear complexity? Much of the material I read about merging heaps takes O(nlogn).

Upvotes: 0

Views: 1989

Answers (2)

Novneet Nov
Novneet Nov

Reputation: 592

We are given two heaps of size N each. Each heap can be represented as an array See relation between parent and child. So we have two arrays which are heap ordered. We need to concatenate these two arrays into one by adding all the elements of one array to the end of the other.

So now we have one array of size 2N but it is not heap ordered. To make an array heap ordered it takes linear number of compares and hence takes linear time. (See bottom-up heap construction - Order of building a heap in O(n))

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372814

There is an O(n)-time algorithm (sometimes called "heapify") that, given n total values, creates a max-heap from those values. This earlier answer describes the algorithm and explains its runtime. You can use this algorithm to merge two max-heaps by creating a new array storing all the values from those max-heaps and applying the heapify algorithm to construct an new heap out of them.

If you know you'll be merging heaps frequently, though, there are better data structures than binary heaps. For example, binomial heaps, pairing heaps, and skew heaps all support melding in O(log n) time.

Hope this helps!

Upvotes: 0

Related Questions