How to Merge two binary Max Heaps in Java

Hey! In this tutorial, we are going to learn how to merge two binary Max Heaps in Java. Before the actual procedure, We will be learning what are Max heaps, what does Binary Max heap refer to? How to implement Binary Max heap for a given array and finally we will learn how to merge two binary Max Heaps using Java Programming.

Java program to merge two binary max heaps and learning the basic definition of heaps

Firstly, we shall understand what heaps are. A heap is a special Tree-Based Data Structure where the tree is complete Binary Tree.

A complete Binary tree is a data structure in which every internal node must have exactly two children and the leaf nodes can have either two children or left child only (If it has to be Complete Binary Tree, leaf nodes can not have the right child without having a corresponding left child). Major applications of the heap are Heap Sort and Priority Queue.

There are two types of Binary Heaps:

  • Max Binary Heap- Heap structure in which the root node is greater than or equal to any of the nodes in the subtree and the same goes for every node and its corresponding subtree.
    Maximum Binary heap
  •  Min Binary Heap- Heap structure in which the root node is smaller than or equal to any of the nodes in the subtree and the same goes for every node and its corresponding subtree.
    minimum binary heap

Our approach to merge two binary max heap will be:

We will copy both the given max binary heap arrays into one array which will take O(n) time complexity and then we will implement a max-heap structure for that given array, which we also call as heapify. The time complexity of heapifying in a tight case is O(n). so our overall complexity of the theorem will be O(n) which is quite satisfying. When we call on the heapify function, it will create a max heap for us using recursion and stores it in the array itself. Our approach is to find the last non-leaf node and then perform heapify in reverse order on each non-leaf node. The index of the last non-leaf node is given by (n/2)-1 where n is the number of nodes.

To build the max heap we will call heapify only on the non-leaf nodes i.e. nodes on the left of the index (n/2)-1 in the given array.

Let’s now implement our code for the same:

public class MergeHeap { 
public static void helper(int mergedArray[], int size, int currentNodeIndex) 
{ 
int rootIndex = currentNodeIndex; // Initialize currentNodeIndex as rootNodeIndex for current subtree. 
int leftChildIndex = 2 * currentNodeIndex + 1; // Finding leftchildIndex of current Node = 2*currentNodeIndex + 1 
int rightChildIndex = 2 * currentNodeIndex + 2; // Finding rightchildIndex of current node= 2*currenNodeIndex + 2 
  
// If left child is greater, make it root.
if (leftChildIndex < size && mergedArray[leftChildIndex] > mergedArray[rootIndex]) 
    rootIndex = leftChildIndex; 
 
// If right child is greater, make it root.
if (rightChildIndex < size && mergedArray[rightChildIndex] > mergedArray[rootIndex]) rootIndex = rightChildIndex; 
  
// Swapping of root if not the largest.
if (rootIndex != currentNodeIndex) { 
    int swap = mergedArray[currentNodeIndex]; 
    mergedArray[currentNodeIndex] = mergedArray[rootIndex]; 
    mergedArray[rootIndex] = swap; 
   
  // Recursively calling helper function on subtree. 
    helper(mergedArray, size, rootIndex); 
    } 
} 
  
    
// Heapify function.
public static void heapify(int mergedArray[], int size) 
{ 
// Index of last non-leaf node 
int lastindex = (size / 2) - 1;

// Performing heapify in reverse order for every index less than last leaf node index. 
for (int i = lastindex; i >= 0; i--) { 
 helper(mergedArray, size, i); 
} 
}     
    
public static void copyArrays(int mergedArray[], int A1[],  int A2[], int m, int n)
{
    // Copy elements of both array to new array. 
for (int i = 0; i < m; i++) 
    mergedArray[i] = A1[i]; 
for (int i = 0; i < n; i++) 
    mergedArray[m + i] = A2[i]; 
// finally calling on heapify function.
heapify(mergedArray, m+n); 
}
 
// Main method
public static void main(String[] args) 
{ 
int A1[] = { 20, 6, 9, 33, 88, 56, 79 }; 
int A2[] = { 81, 100, 45, 37, 11, 67 }; 
int m = A1.length; 
int n = A2.length; 
  
int[] mergedArray = new int[m + n]; 
  
copyArrays(mergedArray, A1, A2, m, n); 
    
System.out.println("After merging two max heaps into one we get:");
  
for (int i = 0; i < m + n; i++) 
    System.out.print(mergedArray[i] + " "); 
System.out.println(); 
    } 
}

Output :

After merging two max heaps into one we get:
100 88 79 81 45 67 9 6 33 20 37 11 56

Thank You.

Article on Building Heap in Java: Build Heap in Java

 

Leave a Reply

Your email address will not be published. Required fields are marked *