I recently took my Computer Science exam and there was a question like that.

There are two max-heaps (array implemented). You need to come up with an algorithm that merges these two max-heaps and creates a new max-heap (array implemented)

Solution of the question is very intuitive that is:

1. Merge two array
2. Call heap rebuild

I looked in the Internet and encountered with same type of solutions.

However, I wrote a solution like that which I could not refute own my own.

My Algorithm

1. Create index1 and index2 which points first element of heapArr1 and heapArr2
2. Create a new heap array which has size of heapArr1.size heapArr2.size
3. In while loop
4. compare index1 element of heapArr1 and index2 element of heapArr2
5. Whichever is greater, write the result array and increment the index of the array that element taken until two arrays all traversed.

For example

Heap1: 12-5 -6-2-3

Heap2: 15-13-4-1-0

We wil first compare 15 and 12. Write 15

resultHeap: 15

Now compare 13 and 12

resultHeap: 15 - 13

Compare 4 and 12

resultHeap: 15 - 13 - 12

Compare 4 and 5

resultHeap: 15 - 13 - 12 - 4

if we go on like that we have

resultHeap: 15 - 13 - 12 - 5 - 6 - 4 - 2 - 3 - 1 - 0. And it is also a heap

Is this algorithm correct? Or can someone gave the refutation data set?

CodePudding user response：

Is this algorithm correct?

No.

can someone gave the refutation data set?

Take this input:

• First Heap: 10, 2, 9

      10
     /  \
    2    9
  

• Second Heap: 8, 1, 4

      8
     / \
    1   4
  

Apply the algorithm -- the brackets indicate the current index in each heap:

      10
     /   \
    8     2
   / \   /
  9   1 4 

The result is not a valid heap as 9 should not be a child of 8, since 9 is greater. And 4 should not be the child of 2, since 4 is greater.

CodePudding user response：

This could be one possible solution for heaps of equal size.

1. Assume 2 max(or min) binary heaps(A and B).
2. First compare the roots, the one which is smaller(assume A) can safely be assumed to be candidate for the subtree of the other one(B), so assign it as any one child of B(assume left)
3. Since B's children are now being replaced you have 2 new heaps to consider i.e B's original children
4. And now you have an empty space i.e the right child of B. Follow this procedure recursively to merge B's chilren and assign the resultant heap as the right child of B.

This is just fancy pointer manipulation and it isn't actually building a heap, rather taking advantage of the fact that you already have heaps.

Apologies for not being able to express it more formally. Please correct me if you find something wrong. This is just the general idea and doesn't consider implementation specific details.