Answer to Question #164603 in Java | JSP | JSF for Al

Question

rite and test a JAVA program that merges two heaps together the output should be a heap 

Answer 1

/*we are going to solve this problem using array representation of Binary Heaps
MaxHeaps can be represented using an array simply
   The root element will be arr[0];
   for ith index
       arr[(i-1)/2] -> parent of that node
       arr[2*i+1] -> left child node
       arr[2*i+2] -> right child node
Root element will be greater than both of its child in case of Max_heap .
we are assuming that two heaps will be provided earlier ... in case of simple array, we will have to convert it into heap first then proceed further.   
*/
class merge_heaps
{
   public static void heapify_function(int[] arr, int size, int index) // This function converts an array into a heap
   {
       if (index >= size)
       {
           return;
       }
       int left = index * 2 + 1;
       int right = index * 2 + 2;
       int max;
       if (left < size && arr[left] > arr[index]) {
           max = left;
       }
       else
           max = index;
       if (right < size && arr[right] > arr[max]) {
           max = right;
       }
       if (max != index) {
           int temp = arr[max];
           arr[max] = arr[index];
           arr[index] = temp;
           heapify_function(arr, size, max); // recursive call
       }
   }
   public static void mergeHeaps(int[] arr, int[] a, int[] b, int n, int m)
   {
       for (int i = 0; i < n; i++) { /// copy first heap element into third array
           arr[i] = a[i];
       }
       for (int i = 0; i < m; i++) { //// copy second heap element into third array
           arr[n + i] = b[i];
       }
       n = n + m;
       for (int i = n / 2 - 1; i >= 0; i--) {
           heapify_function(arr, n, i); // convert that formed array into a heap
       }
   }
  
   public static void main(String[] args)
   {
       int[] a = {10, 5, 6, 2}; // first heap ... it can be dynamic ass well
       int[] b = {12, 7, 9}; // second heap
       int n = a.length;
       int m = b.length;


       int[] merged = new int[m + n]; // array to store merge form


       mergeHeaps(merged, a, b, n, m);


       for (int i = 0; i < m + n; i++)
           System.out.print(merged[i] + " ");
       System.out.println();
   }
}
/*Time Complexity Analysis :
   In array representation of heap , we just have to traverse the array which takes liner time in case of array
   For first heap -> O(m)
   for second Heap -> O(n)
   For whole algorithm , complexity=O(m+n)
  
*/