Merge two sorted arrays in O ( 1 ) extra space using Heap | Java program to implement the above approach ; Function to perform min heapify on array brr [ ] ; Stores index of left child of i . ; Stores index of right child of i . ; Stores index of the smallest element in ( arr [ i ] , arr [ left ] , arr [ right ] ) ; Check if arr [ left ] less than arr [ smallest ] ; Update smallest ; Check if arr [ right ] less than arr [ smallest ] ; Update smallest ; if i is not the index of smallest element ; Swap arr [ i ] and arr [ smallest ] ; Perform heapify on smallest ; Function to merge two sorted arrays ; Traverse the array arr [ ] ; Check if current element is less than brr [ 0 ] ; Swap arr [ i ] and brr [ 0 ] ; Perform heapify on brr [ ] ; Sort array brr [ ] ; Function to print array elements ; Traverse array arr [ ] ; Driver Code ; Function call to merge two array ; Print first array ; Print Second array .
import java . util . * ; class GFG { static void minHeapify ( int brr [ ] , int i , int M ) { int left = 2 * i + 1 ; int right = 2 * i + 2 ; int smallest = i ; if ( left < M && brr [ left ] < brr [ smallest ] ) { smallest = left ; } if ( right < M && brr [ right ] < brr [ smallest ] ) { smallest = right ; } if ( smallest != i ) { int temp = brr [ i ] ; brr [ i ] = brr [ smallest ] ; brr [ smallest ] = temp ; minHeapify ( brr , smallest , M ) ; } } static void merge ( int arr [ ] , int brr [ ] , int N , int M ) { for ( int i = 0 ; i < N ; ++ i ) { if ( arr [ i ] > brr [ 0 ] ) { int temp = arr [ i ] ; arr [ i ] = brr [ 0 ] ; brr [ 0 ] = temp ; minHeapify ( brr , 0 , M ) ; } } Arrays . sort ( brr ) ; } static void printArray ( int arr [ ] , int N ) { for ( int i = 0 ; i < N ; i ++ ) System . out . print ( arr [ i ] + " ▁ " ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 23 , 35 , 235 , 2335 } ; int brr [ ] = { 3 , 5 } ; int N = arr . length ; int M = brr . length ; merge ( arr , brr , N , M ) ; printArray ( arr , N ) ; printArray ( brr , M ) ; } }