Is it possible to build a max heap from two heap without rebuilding the heap?

Question

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?

Answer 1

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:

Heap 1	Heap 2	Result heap
[10],2,9	[8],1,4	10
10,[2],9	[8],1,4	10,8
10,[2],9	8,[1],4	10,8,2
10,2,[9]	8,[1],4	10,8,2,9 (violation)
10,2,9[]	8,[1],4	10,8,2,9,1
10,2,9[]	8,1,[4]	10,8,2,9,1,4 (violation)

      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.