Skip to main content

Merge two binary min heap arrays

Here given code implementation process.

//C Program
//Merge two binary min heap arrays
#include <stdio.h>

//Swap two element in array
void swap(int arr[],int first,int second)
{
  int auxiliary=arr[first];
  arr[first]=arr[second];
  arr[second]=auxiliary;
}
//Check if given element is from of min heap or not
// If not a min heap then swap node value
int compare(int arr[],int left,int right,int root,int size)
{
  int location = -1;

  if(left < size &&  arr[left] < arr[root] )
  {

    if(right < size && arr[right] < arr[left])
    {
      swap(arr,right,root);
      location = right;
    }
    else
    {
      swap(arr,left,root);
      location = left;
    }
  }
  else if(right < size && arr[right] < arr[root])
  {
    swap(arr,right,root);
    location = right;
  }
  return location;
}
void heap(int arr[],int size,int root)
{
  int left  = 2*root+1;
  int right = 2*root+2;
 
  int next = compare(arr, left, right, root, size);
 
  if(next != -1)
  {
    heap(arr,size,next);
  }
}
void printData(int arr[],int size)
{
  printf("\n");
  for(int i = 0; i < size; i++)
  {
    printf("%3d",arr[i] );
  }
}

void merge(int arr[],int size)
{
  for (int i = (size/2)-1; i >= 0; i--)
  {
    heap(arr,size,i);
  }
}
int main()

{
    int heap1[] = { 1, 5, 6, 9, 7, 8, 10}; 
    int heap2[] = { 3, 4, 5, 11 }; 
  
    int n = sizeof(heap1) / sizeof(heap1[0]); 
    int m = sizeof(heap2) / sizeof(heap2[0]); 

    //new memory for combine min heap elements
    int combine[n+m];

    //assign first heap array element
    for (int i = 0; i < n; ++i)
    {
      combine[i]=heap1[i];
    }
    //assign second heap array element
    for (int i = 0; i < m; ++i)
    {
      combine[n+i]=heap2[i];
    }
    merge(combine,n+m);
    /*
        After marge

              1
           /      \
          3        6
         /  \     / \
        4     5  8   10
       / \   / \
      9   5 7  11
    */
    printData(combine,n+m);
  return 0;
}

Output

  1  3  6  4  5  8  10  9  5  7  11
/*
 C++ Program
 Merge two binary min heap arrays
*/

#include<iostream>

using namespace std;
class MinHeap {
  public:
    void swap(int arr[], int first, int second) {
      int auxiliary = arr[first];
      arr[first] = arr[second];
      arr[second] = auxiliary;
    }
  int compare(int arr[], int left, int right, int root, int size) {
    int location = -1;
    if (left < size && arr[left] < arr[root]) {
      if (right < size && arr[right] < arr[left]) {
        this->swap(arr, right, root);
        location = right;
      } else {
        this->swap(arr, left, root);
        location = left;
      }
    } else
    if (right < size && arr[right] < arr[root]) {
      this->swap(arr, right, root);
      location = right;
    }
    return location;
  }
  void heap(int arr[], int size, int root) {
    int left = 2 *root + 1;
    int right = 2 *root + 2;
    int next = this->compare(arr, left, right, root, size);
    if (next != -1) {
      this->heap(arr, size, next);
    }
  }
  void printData(int arr[], int size) {
    cout << "\n";
    for (int i = 0; i < size; i++) {
      cout << "  " << arr[i];
    }
  }
  void merge(int arr[], int size) {
    for (int i = (size / 2) - 1; i >= 0; i--) {
      this->heap(arr, size, i);
    }
  }
};
int main() {
  MinHeap obj ;
  int heap1[] = { 1, 5, 6, 9, 7, 8, 10}; 
  int heap2[] = { 3, 4, 5, 11 }; 
  int n = sizeof(heap1)/sizeof(heap1[0]);
  int m = sizeof(heap2)/sizeof(heap2[0]);
  int combine[n + m];
  for (int i = 0; i < n; ++i) {
    combine[i] = heap1[i];
  }
  for (int i = 0; i < m; ++i) {
    combine[n + i] = heap2[i];
  }
  obj.merge(combine, n + m);
  /*
      After marge

            1
         /      \
        3        6
       /  \     / \
      4     5  8   10
     / \   / \
    9   5 7  11
  */
  obj.printData(combine, n + m);
  return 0;
}

Output

  1  3  6  4  5  8  10  9  5  7  11
/*
  Java program
  Merge two binary Min heap arrays
*/

public class MinHeap {

  //Swap two element in array
  void swap(int []arr, int first, int second) {
    int auxiliary = arr[first];
    arr[first] = arr[second];
    arr[second] = auxiliary;
  }
  //Check if given element is from of Min heap or not
  //If not a Min heap then swap node value
  int compare(int []arr, int left, int right, int root, int size) {
    int location = -1;

    if (left < size && arr[left] < arr[root]) {

      if (right < size && arr[right] < arr[left]) {
        swap(arr, right, root);
        location = right;
      } else {
        swap(arr, left, root);
        location = left;
      }
    } else if (right < size && arr[right] < arr[root]) {
      swap(arr, right, root);
      location = right;
    }
    return location;
  }
  void heap(int []arr, int size, int root) {
    int left = 2 *root + 1;
    int right = 2 *root + 2;

    int next = compare(arr, left, right, root, size);

    if (next != -1) {
      heap(arr, size, next);
    }
  }
  void printData(int []arr, int size) {
    System.out.print("\n");
    for (int i = 0; i < size; i++) {
      System.out.print("  "+arr[i]);
    }
  }

  void merge(int []arr, int size) {
    for (int i = (size / 2) - 1; i >= 0; i--) {
      heap(arr, size, i);
    }
  }
  public static void main(String[] args) {

    MinHeap obj = new MinHeap();
    int []heap1 = { 1, 5, 6, 9, 7, 8, 10 }; 
    int []heap2 = { 3, 4, 5, 11 }; 
  
    int n = heap1.length; 
    int m = heap2.length; 

    //New memory for combine Min heap elements
    int []combine=new int[n+m];

    //Assign first heap array element
    for (int i = 0; i < n; ++i)
    {
      combine[i] = heap1[i];
    }
    //Assign second heap array element
    for (int i = 0; i < m; ++i)
    {
      combine[n+i]=heap2[i];
    }
    obj.merge(combine,n+m);
    /*
        After marge

              1
           /      \
          3        6
         /  \     / \
        4     5  8   10
       / \   / \
      9   5 7  11
    */
    obj.printData(combine,n+m);
  }
}

Output

  1  3  6  4  5  8  10  9  5  7  11
/*
  C# program
  Merge two binary Min heap arrays
*/
using System;
public class MinHeap {

	//Swap two element in array
	void swap(int []arr, int first, int second) {
		int auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	//Check if given element is from of Min heap or not
	//If not a Min heap then swap node value
	int compare(int []arr, int left, int right, int root, int size) {
		int location = -1;

		if (left < size && arr[left] < arr[root]) {

			if (right < size && arr[right] < arr[left]) {
				swap(arr, right, root);
				location = right;
			} else {
				swap(arr, left, root);
				location = left;
			}
		} else if (right < size && arr[right] < arr[root]) {
			swap(arr, right, root);
			location = right;
		}
		return location;
	}
	void heap(int []arr, int size, int root) {
		int left = 2 *root + 1;
		int right = 2 *root + 2;

		int next = compare(arr, left, right, root, size);

		if (next != -1) {
			heap(arr, size, next);
		}
	}
	void printData(int []arr, int size) {
		Console.Write("\n");
		for (int i = 0; i < size; i++) {
			Console.Write("  "+arr[i]);
		}
	}

	void merge(int []arr, int size) {
		for (int i = (size / 2) - 1; i >= 0; i--) {
			heap(arr, size, i);
		}
	}
	public static void Main(String[] args) {

		MinHeap obj = new MinHeap();
		int []heap1 = { 1, 5, 6, 9, 7, 8, 10 }; 
		int []heap2 = { 3, 4, 5, 11 }; 

		int n = heap1.Length; 
		int m = heap2.Length; 

		//New memory for combine Min heap elements
		int []combine=new int[n+m];

		//Assign first heap array element
		for (int i = 0; i < n; ++i)
		{
			combine[i] = heap1[i];
		}
		//Assign second heap array element
		for (int i = 0; i < m; ++i)
		{
			combine[n+i]=heap2[i];
		}
		obj.merge(combine,n+m);
		/*
        After marge

              1
           /      \
          3        6
         /  \     / \
        4     5  8   10
       / \   / \
      9   5 7  11
    */
		obj.printData(combine,n+m);
	}
}

Output

  1  3  6  4  5  8  10  9  5  7  11
# Python 3 Program
# Merge two binary min heap arrays

class MinHeap :

  def swap(self, arr, first, second) :
    auxiliary = arr[first]
    arr[first] = arr[second]
    arr[second] = auxiliary
  
  def compare(self, arr, left, right, root, size) :
    location = -1
    if (left < size and arr[left] < arr[root]) :
      if (right < size and arr[right] < arr[left]) :
        self.swap(arr, right, root)
        location = right
      else :
        self.swap(arr, left, root)
        location = left
      
    elif (right < size and arr[right] < arr[root]) :
      self.swap(arr, right, root)
      location = right
    
    return location
  
  def heap(self, arr, size, root) :
    left = 2 * root + 1
    right = 2 * root + 2
    next = self.compare(arr, left, right, root, size)
    if (next != -1) :
      self.heap(arr, size, next)
    
  
  def printData(self, arr, size) :
    print(end="\n")
    i = 0
    while (i < size) :
      print(" ", arr[i],end="")
      i += 1
    
  
  def merge(self, arr, size) :
    i = int(size / 2) - 1
    while (i >= 0) :
      self.heap(arr, size, i)
      i -= 1
    
  

def main() :
  obj =  MinHeap()
  heap1 = [1, 5, 6, 9, 7, 8, 10]
  heap2 = [3, 4, 5, 11]
  n = len(heap1)
  m = len(heap2)
  combine = [0]*(m+n)
  i = 0
  while (i < n) :
    combine[i] = heap1[i]
    i += 1
  
  i = 0
  while (i < m) :
    combine[n + i] = heap2[i]
    i += 1
  
  obj.merge(combine, n + m)
  #
  #      After marge
  #            1
  #         /      \
  #        3        6
  #       /  \     / \
  #      4     5  8   10
  #     / \   / \
  #    9   5 7  11
  #   
  obj.printData(combine, n + m)

if __name__ == "__main__":
  main()

Output

  1  3  6  4  5  8  10  9  5  7  11
# Ruby Program
# Merge two binary min heap arrays

class MinHeap 
	def swap(arr, first, second) 
		auxiliary = arr[first]
		arr[first] = arr[second]
		arr[second] = auxiliary
	end
	def compare(arr, left, right, root, size) 
		location = -1
		if (left < size and arr[left] < arr[root]) 
			if (right < size and arr[right] < arr[left]) 
				self.swap(arr, right, root)
				location = right
			else 
				self.swap(arr, left, root)
				location = left
			end
		elsif (right < size and arr[right] < arr[root]) 
			self.swap(arr, right, root)
			location = right
		end
		return location
	end
	def heap(arr, size, root) 
		left = 2 * root + 1
		right = 2 * root + 2
		next_node = self.compare(arr, left, right, root, size)
		if (next_node != -1) 
			self.heap(arr, size, next_node)
		end
	end
	def printData(arr, size) 
		print("\n")
		i = 0
		while (i < size) 
			print("  ", arr[i])
			i += 1
		end
	end
	def merge(arr, size) 
		i = (size / 2) - 1
		while (i >= 0) 
			self.heap(arr, size, i)
			i -= 1
		end
	end
end
def main() 
	obj = MinHeap.new()
	heap1 = [ 1, 5, 6, 9, 7, 8, 10 ]
	heap2 = [3, 4, 5, 11]
	n = heap1.length
	m = heap2.length
	combine = Array.new(n+m,0)
	i = 0
	while (i < n) 
		combine[i] = heap1[i]
		i += 1
	end
	i = 0
	while (i < m) 
		combine[n + i] = heap2[i]
		i += 1
	end
	obj.merge(combine, n + m)
	#
	#      After marge
	#
	#            1
	#         /      \
	#        3        6
	#       /  \     / \
	#      4     5  8   10
	#     / \   / \
	#    9   5 7  11
	#  
	obj.printData(combine, n + m)
end
main()

Output

  1  3  6  4  5  8  10  9  5  7  11
<?php

/*
 Php Program
 Merge two binary Min heap arrays
*/

class MinHeap {
  function swap(&$arr, $first, $second) {
    $auxiliary = $arr[$first];
    $arr[$first] = $arr[$second];
    $arr[$second] = $auxiliary;
  }

  function compare(&$arr, $left, $right, $root, $size) {
    $location = -1;
    if ($left < $size && $arr[$left] < $arr[$root]) {
      if ($right < $size && $arr[$right] < $arr[$left]) {
        $this->swap($arr, $right, $root);
        $location = $right;
      } else {
        $this->swap($arr, $left, $root);
        $location = $left;
      }
    } else
    if ($right < $size && $arr[$right] < $arr[$root]) {
      $this->swap($arr, $right, $root);
      $location = $right;
    }
    return $location;
  }

  function heap(&$arr, $size, $root) {
    $left = 2 *$root + 1;
    $right = 2 *$root + 2;
    $next = $this->compare($arr, $left, $right, $root, $size);
    if ($next != -1) {
      $this->heap($arr, $size, $next);
    }
  }

  function printData($arr, $size) {
    echo("\n");
    for ($i = 0; $i < $size; $i++) {
      echo("  ". $arr[$i]);
    }
  }

  function merge(&$arr, $size) {
    for ($i = intval($size / 2) - 1; $i >= 0; $i--) {
      $this->heap($arr, $size, $i);
    }
  }
}

function main() {
  $obj = new MinHeap();
  $heap1 = array(1, 5, 6, 9, 7, 8, 10);
  $heap2 = array(3, 4, 5, 11);
  $n = count($heap1) ;
  $m = count($heap2) ;
  $combine = array_fill(0, $n+$m, 0);
  for ($i = 0; $i < $n; ++$i) {
    $combine[$i] = $heap1[$i];
  }
  for ($i = 0; $i < $m; ++$i) {
    $combine[$n + $i] = $heap2[$i];
  }
  $obj->merge($combine, $n + $m);
  /*
      After marge

            1
         /      \
        3        6
       /  \     / \
      4     5  8   10
     / \   / \
    9   5 7  11
  */  
  $obj->printData($combine, $n + $m);
}
main();

Output

  1  3  6  4  5  8  10  9  5  7  11
/*
 Node Js Program
 Merge two binary Min heap arrays
*/

class MinHeap {
	swap(arr, first, second) {
		var auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	compare(arr, left, right, root, size) {
		var location = -1;
		if (left < size && arr[left] < arr[root]) {
			if (right < size && arr[right] < arr[left]) {
				this.swap(arr, right, root);
				location = right;
			} else {
				this.swap(arr, left, root);
				location = left;
			}
		} else
		if (right < size && arr[right] < arr[root]) {
			this.swap(arr, right, root);
			location = right;
		}
		return location;
	}
	heap(arr, size, root) {
		var left = 2 *root + 1;
		var right = 2 *root + 2;
		var next = this.compare(arr, left, right, root, size);
		if (next != -1) {
			this.heap(arr, size, next);
		}
	}
	printData(arr, size) {
		process.stdout.write("\n");
		for (var i = 0; i < size; i++) {
			process.stdout.write("  " + arr[i]);
		}
	}
	merge(arr, size) {
		for (var i = parseInt(size / 2) - 1; i >= 0; i--) {
			this.heap(arr, size, i);
		}
	}
}

function main() {
	var obj = new MinHeap();
	var heap1 = [ 1, 5, 6, 9, 7, 8, 10 ];
	var heap2 = [ 3, 4, 5, 11 ];
	var n = heap1.length;
	var m = heap2.length;
	var combine = Array(n + m).fill(0);
	for (var i = 0; i < n; ++i) {
		combine[i] = heap1[i];
	}
	for (var i = 0; i < m; ++i) {
		combine[n + i] = heap2[i];
	}
	obj.merge(combine, n + m);
    /*
        After marge

              1
           /      \
          3        6
         /  \     / \
        4     5  8   10
       / \   / \
      9   5 7  11
    */
	obj.printData(combine, n + m);
}

main();

Output

  1  3  6  4  5  8  10  9  5  7  11
/*
 Swift 4 Program
 Merge two binary Min heap arrays
*/

class MinHeap {
  func swap(_ arr: inout [Int] , _ first : Int, _ second: Int) {
    let auxiliary: Int = arr[first];
    arr[first] = arr[second];
    arr[second] = auxiliary;
  }
  func compare(_ arr: inout [Int] , _ left : Int, _ right: Int, _ root: Int, _ size: Int) -> Int{
    var location: Int = -1;
    if (left < size && arr[left] < arr[root]) {
      if (right < size && arr[right] < arr[left]) {
        self.swap(&arr, right, root);
        location = right;
      } else {
        self.swap(&arr, left, root);
        location = left;
      }
    } else
    if (right < size && arr[right] < arr[root]) {
      self.swap(&arr, right, root);
      location = right;
    }
    return location;
  }
  func heap(_ arr: inout [Int] , _ size : Int, _ root: Int) {
    let left: Int = 2 * root + 1;
    let right: Int = 2 * root + 2;
    let next: Int = self.compare(&arr, left, right, root, size);
    if (next != -1) {
      self.heap(&arr, size, next);
    }
  }
  func printData(_ arr: [Int] , _ size : Int) {
    print(terminator:"\n");
    var i: Int = 0;
    while (i < size) {
      print(" ", arr[i],terminator:"");
      i += 1;
    }
  }
  func merge(_ arr: inout [Int] , _ size : Int) {
    var i: Int = (size / 2) - 1;
    while (i >= 0) {
      self.heap(&arr, size, i);
      i -= 1;
    }
  }
}
func main() {
  let obj: MinHeap = MinHeap();
  let heap1: [Int] = [ 1, 5, 6, 9, 7, 8, 10 ];
  let heap2: [Int] = [ 3, 4, 5, 11 ];
  let n: Int = heap1.count;
  let m: Int = heap2.count;
  var combine: [Int] = Array(repeating:0,count:n+m);
  var i: Int = 0;
  while (i < n) {
    combine[i] = heap1[i];
    i += 1;
  }
  i = 0;
  while (i < m) {
    combine[n + i] = heap2[i];
    i += 1;
  }
  obj.merge(&combine, n + m);
  /*
      After marge

            1
         /      \
        3        6
       /  \     / \
      4     5  8   10
     / \   / \
    9   5 7  11
  */
  obj.printData(combine, n + m);
}
main();

Output

  1  3  6  4  5  8  10  9  5  7  11
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment