Max Heap - Merge Two Max Heap

MergeMaxHeap.java

// the code works not only for mergeing two max heaps but to heapify array in O(n).
// the root is indexed at 1 instead of 0
class MergeMaxHeap {
	public static void maxHeapify(int[] arr, int n, int i) {
		// if index is out of range
		if (i >= n) {
			return;
		}
		int l = i * 2;
		int r = i * 2 + 1;
		int max = i;

		// find the largest element of left and right
		if (l < n && arr[l] > arr[i]) {
			max = l;
		}
		
		if (r < n && arr[r] > arr[max]) {
			max = r;
		}
		
		// swap the maximum value if found
		if (max != i) {
			int temp = arr[max];
			arr[max] = arr[i];
			arr[i] = temp;
			// we call maxHeapify again with `max`. This is because since we moved a lower value down, 
			// the heapify property that was previously valid at that node might have been disturbed.
			// so we recursively heapify the node and nodes below that.
			maxHeapify(arr, n, max);
		}
	}

	public static void mergeHeaps(int[] arr, int[] a, int[] b, int n, int m) {
		arr[0] = -1;
		for (int i = 0; i < n; i++) {
			arr[i+1] = a[i];
		}
		 
		for (int i = 0; i < m; i++) {
			arr[n + i + 1] = b[i];
		}
		n = n + m + 1;
		// when we start, we pick the last root node which is (n/2 - 1)
		// we check if the node follows the heap property. If not then swap it.
		// System.out.println(" s " + (n));
		for (int i = n / 2 - 1; i > 0; i--) {
			maxHeapify(arr, n, i);
		}
		 display(arr);
	}

	public static void display(int arr[]) {
		for (int i = 1; i < arr.length; i++) {
			System.out.print(" " + arr[i]);
		}
		System.out.println(" ");
	}

	public static void main(String[] args) {
		int[] a = { 10, 5 , 6 , 2 };
		int[] b = { 12, 7, 9};
		int n = a.length;
		int m = b.length;
		// + 1 because starting the heap from 1 instead of 0
		int[] merged = new int[m + n + 1];
		mergeHeaps(merged, a, b, n, m);
	}
}