Min heap to max heap conversion

Here given code implementation process.

//C Program
//Min heap to max heap conversion
#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;
}
//Compare the properties of max heap
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);
  }
}
//print array elements
void print_data(int arr[],int size)
{
  
  for(int i = 0; i < size; i++)
  {
    printf("%3d",arr[i] );
  }
  printf("\n");
}

void max_heap(int arr[],int size)
{
  for (int i = (size/2)-1; i >= 0; i--)
  {
    heap(arr,size,i);
  }
}
int main()
{
  
  /*
         1
       /    \
      5      6
     / \    / \
    9   7  8   10
   / \
  16  18 

  */
  int heap_data[] = { 1, 5, 6, 9, 7, 8, 10, 16 , 18}; 

  //Get the size of array
  int n = sizeof(heap_data) / sizeof(heap_data[0]); 

  printf("  Min heap : \n");

  print_data(heap_data,n);
  
  max_heap(heap_data,n);
  /*
         18
       /    \
      16    10
     / \    / \
    9   7  8   6
   / \
  5   1 

  */
  printf("  Max heap : \n");
  print_data(heap_data,n);
  return 0;
}

Output

  Min heap :
  1  5  6  9  7  8 10 16 18
  Max heap :
 18 16 10  9  7  8  6  5  1
/*
  C++ Program
  Max heap to min heap conversion
*/
#include<iostream>

using namespace std;
class MyHeap {
	public:

    //Swap two element in array
    void swap(int arr[], int first, int second) {
      int auxiliary = arr[first];
      arr[first] = arr[second];
      arr[second] = auxiliary;
    }
	//Compare the properties of max heap
	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);
		}
	}
	//print array elements
	void print_data(int arr[], int size) {
		for (int i = 0; i < size; i++) {
			cout << " " << arr[i];
		}
		cout << "\n";
	}
	void max_heap(int arr[], int size) {
		for (int i = (size / 2) - 1; i >= 0; i--) {
			this->heap(arr, size, i);
		}
	}
};
int main() {
	MyHeap obj = MyHeap();
	int heap_data[] = {
		1,
		5,
		6,
		9,
		7,
		8,
		10,
		16,
		18
	};
	//Get the size of array
	int n = sizeof(heap_data) / sizeof(heap_data[0]);
	cout << " Min heap : \n";
	obj.print_data(heap_data, n);
	obj.max_heap(heap_data, n);
	/*
	           18
	         /    \
	        16    10
	       / \    / \
	      9   7  8   6
	     / \
	    5   1 

	    */

	cout << " Max heap : \n";
	obj.print_data(heap_data, n);
	return 0;
}

Output

 Min heap :
 1 5 6 9 7 8 10 16 18
 Max heap :
 18 16 10 9 7 8 6 5 1
/*
  Java Program
  Max heap to min heap conversion
*/
public class MyHeap {
  
  //Swap two element in array
  public void swap(int []arr,int first,int second)
  {
    int auxiliary=arr[first];
    arr[first]=arr[second];
    arr[second]=auxiliary;
  }
  //Compare the properties of max heap
  public 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;
  }

  public 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);
    }
  }
  //print array elements
  public void print_data(int []arr,int size)
  {
    
    for(int i = 0; i < size; i++)
    {
      System.out.print("  "+arr[i] );
    }
    System.out.print("\n");
  }

  public void max_heap(int []arr,int size)
  {
    for (int i = (size/2)-1; i >= 0; i--)
    {
      heap(arr,size,i);
    }
  }
  public static void main(String[] args) {
    
    MyHeap obj = new MyHeap();
      
    /*
           1
         /    \
        5      6
       / \    / \
      9   7  8   10
     / \
    16  18 

    */
    int []heap_data = { 1, 5, 6, 9, 7, 8, 10, 16 , 18}; 

    //Get the size of array
    int n = heap_data.length; 

    System.out.print("  Min heap : \n");

    obj.print_data(heap_data,n);
    
    obj.max_heap(heap_data,n);
    /*
           18
         /    \
        16    10
       / \    / \
      9   7  8   6
     / \
    5   1 

    */
    System.out.print("  Max heap : \n");
    obj.print_data(heap_data,n);

  } 
}

Output

 Min heap :
 1 5 6 9 7 8 10 16 18
 Max heap :
 18 16 10 9 7 8 6 5 1
/*
  C# Program
  Max heap to min heap conversion
*/
using System;

public class MyHeap {
	//Swap two element in array
	public void swap(int[] arr, int first, int second) {
		int auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	//Compare the properties of max heap
	public 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;
	}
	public 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);
		}
	}
	//print array elements
	public void print_data(int[] arr, int size) {
		for (int i = 0; i < size; i++) {
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	public void max_heap(int[] arr, int size) {
		for (int i = (size / 2) - 1; i >= 0; i--) {
			heap(arr, size, i);
		}
	}
	public static void Main(String[] args) {
		MyHeap obj = new MyHeap();
       /*
		           1
		         /    \
		        5      6
		       / \    / \
		      9   7  8   10
		     / \
		    16  18 

		*/
		int[] heap_data = {
			1,
			5,
			6,
			9,
			7,
			8,
			10,
			16,
			18
		};
		//Get the size of array
		int n = heap_data.Length;
		Console.Write(" Min heap : \n");
		obj.print_data(heap_data, n);
		obj.max_heap(heap_data, n);
		Console.Write(" Max heap : \n");
		obj.print_data(heap_data, n);
	}
}

Output

 Min heap :
 1 5 6 9 7 8 10 16 18
 Max heap :
 18 16 10 9 7 8 6 5 1
<?php
/*
  Php Program
  Max heap to min heap conversion
*/
class MyHeap {
	//Swap two element in array

	public 	function swap(&$arr, $first, $second) {
		$auxiliary = $arr[$first];
		$arr[$first] = $arr[$second];
		$arr[$second] = $auxiliary;
	}
	//Compare the properties of max heap

	public 	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;
	}
	public 	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);
		}
	}
	//print array elements

	public 	function print_data($arr, $size) {
		for ($i = 0; $i < $size; $i++) {
			echo(" ". $arr[$i]);
		}
		echo("\n");
	}
	public 	function max_heap(&$arr, $size) {
		for ($i = (intval($size / 2)) - 1; $i >= 0; $i--) {
			$this->heap($arr, $size, $i);
		}
	}
}

function main() {
	$obj = new MyHeap();
	/*
	           1
	         /    \
	        5      6
	       / \    / \
	      9   7  8   10
	     / \
	    16  18 

	    */
	$heap_data = array(1, 5, 6, 9, 7, 8, 10, 16, 18);
	//Get the size of array
	$n = count($heap_data);
	echo(" Min heap : \n");
	$obj->print_data($heap_data, $n);
	$obj->max_heap($heap_data, $n);
	/*
	           18
	         /    \
	        16    10
	       / \    / \
	      9   7  8   6
	     / \
	    5   1 

	    */

	echo(" Max heap : \n");
	$obj->print_data($heap_data, $n);

}
main();

Output

 Min heap :
 1 5 6 9 7 8 10 16 18
 Max heap :
 18 16 10 9 7 8 6 5 1
/*
  Node Js Program
  Max heap to min heap conversion
*/
class MyHeap {
	//Swap two element in array
	swap(arr, first, second) {
		var auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}

	//Compare the properties of max heap
	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);
		}
	}

	//print array elements
	print_data(arr, size) {
		for (var i = 0; i < size; i++) {
			process.stdout.write(" " + arr[i]);
		}

		process.stdout.write("\n");
	}
	max_heap(arr, size) {
		for (var i = (parseInt(size / 2)) - 1; i >= 0; i--) {
			this.heap(arr, size, i);
		}
	}
}

function main(args) {
	var obj = new MyHeap();
	/*
	           1
	         /    \
	        5      6
	       / \    / \
	      9   7  8   10
	     / \
	    16  18 

	    */
	var heap_data = [1, 5, 6, 9, 7, 8, 10, 16, 18];
	//Get the size of array
	var n = heap_data.length;
	process.stdout.write(" Min heap : \n");
	obj.print_data(heap_data, n);
	obj.max_heap(heap_data, n);
	/*
	           18
	         /    \
	        16    10
	       / \    / \
	      9   7  8   6
	     / \
	    5   1 

	    */

	process.stdout.write(" Max heap : \n");
	obj.print_data(heap_data, n);
}

main();

Output

 Min heap :
 1 5 6 9 7 8 10 16 18
 Max heap :
 18 16 10 9 7 8 6 5 1
#  Python 3 Program
#  Max heap to min heap conversion

class MyHeap :
	# Swap two element in array
	def swap(self, arr, first, second) :
		auxiliary = arr[first]
		arr[first] = arr[second]
		arr[second] = auxiliary
	 # Compare the properties of max heap
	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)
		
	 # print array elements
	def print_data(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	def max_heap(self, arr, size) :
		i = (int(size / 2)) - 1
		while (i >= 0) :
			self.heap(arr, size, i)
			i -= 1
		
	

def main() :
	obj = MyHeap()
	#
	#               1
	#             /    \
	#            5      6
	#           / \    / \
	#          9   7  8   10
	#         / \
	#        16  18 
	#        
	
	heap_data = [1, 5, 6, 9, 7, 8, 10, 16, 18] 
	# Get the size of array
	n = len(heap_data)
	print(" Min heap : \n", end = "")
	obj.print_data(heap_data, n)
	obj.max_heap(heap_data, n)
	print(" Max heap : \n", end = "")
	obj.print_data(heap_data, n)


if __name__ == "__main__":
	main()

Output

 Min heap :
  1  5  6  9  7  8  10  16  18
 Max heap :
  18  16  10  9  7  8  6  5  1
#  Ruby Program
#  Max heap to min heap conversion

class MyHeap 
	 # Swap two element in array
	def swap(arr, first, second) 
		auxiliary = arr[first]
		arr[first] = arr[second]
		arr[second] = auxiliary
	end
	 # Compare the properties of max heap
	def compare(arr, left, right, root, size) 
		location = -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
			end
		elsif (right < size && 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_in = self.compare(arr, left, right, root, size)
		if (next_in != -1) 
			self.heap(arr, size, next_in)
		end
	end
	 # print array elements
	def print_data(arr, size) 
		i = 0
		while (i < size) 
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	def max_heap(arr, size) 
		i = (size / 2) - 1
		while (i >= 0) 
			self.heap(arr, size, i)
			i -= 1
		end
	end
end
def main() 
	obj = MyHeap.new()
	#
	#               1
	#             /    \
	#            5      6
	#           / \    / \
	#          9   7  8   10
	#         / \
	#        16  18 
	#        
	
	heap_data = [1, 5, 6, 9, 7, 8, 10, 16, 18]
	 # Get the size of array
	n = heap_data.length
	print(" Min heap  :\n")
	obj.print_data(heap_data, n)
	obj.max_heap(heap_data, n)
	#
	#               18
	#             /    \
	#            16    10
	#           / \    / \
	#          9   7  8   6
	#         / \
	#        5   1 
	#        
	

	print(" Max heap  :\n")
	obj.print_data(heap_data, n)
end
main()

Output

 Min heap  :
 1 5 6 9 7 8 10 16 18
 Max heap  :
 18 16 10 9 7 8 6 5 1
/*
  Scala Program
  Max heap to min heap conversion
*/
class MyHeap {
	//Swap two element in array
	def swap(arr: Array[Int], first: Int, second: Int): Unit = {
		val auxiliary: Int = arr(first);
		arr(first) = arr(second);
		arr(second) = auxiliary;
	}
	//Compare the properties of max heap
	def compare(arr: Array[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)) {
				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;
	}
	def heap(arr: Array[Int], size: Int, root: Int): Unit = {
		val left: Int = 2 * root + 1;
		val right: Int = 2 * root + 2;
		val next: Int = this.compare(arr, left, right, root, size);

		if (next != -1) {
			this.heap(arr, size, next);
		}
	}
	//print array elements
	def print_data(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size) {
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	def max_heap(arr: Array[Int], size: Int): Unit = {
		var i: Int = ((size / 2).toInt) - 1;
		while (i >= 0) {
			this.heap(arr, size, i);
			i -= 1;
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MyHeap = new MyHeap();

		/*
		               1
		             /    \
		            5      6
		           / \    / \
		          9   7  8   10
		         / \
		        16  18 

		        */
		var heap_data: Array[Int] = Array(1, 5, 6, 9, 7, 8, 10, 16, 18);

		//Get the size of array
		val n: Int = heap_data.length;
		print(" Min heap : \n");
		obj.print_data(heap_data, n);
		obj.max_heap(heap_data, n);

		/*
		               18
		             /    \
		            16    10
		           / \    / \
		          9   7  8   6
		         / \
		        5   1 

		        */
		print(" Max heap : \n");
		obj.print_data(heap_data, n);
	}
}

Output

 Min heap :
 1 5 6 9 7 8 10 16 18
 Max heap :
 18 16 10 9 7 8 6 5 1
/*
  Swift Program
  Max heap to min heap conversion
*/
class MyHeap {
	//Swap two element in array
	func swap(_ arr: inout [Int], _ first: Int, _ second: Int) {
		let auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	//Compare the properties of max heap
	func compare(_ arr: inout [Int], _ left: Int, _ right: Int, _ root: Int, _ size: Int) -> Int {
		var location = -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 = 2 * root + 1;
		let right = 2 * root + 2;
		let next = self.compare(&arr, left, right, root, size);
		if (next != -1) {
			self.heap(&arr, size, next);
		}
	}
	//print array elements
	func print_data(_ arr: [Int], _ size: Int) {
		var i = 0;
		while (i < size) {
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	func max_heap(_ arr: inout [Int], _ size: Int) {
		var i = (size / 2) - 1;
		while (i >= 0) {
			self.heap(&arr, size, i);
			i -= 1;
		}
	}
}
func main() {
	let obj = MyHeap();
	/*
	               1
	             /    \
	            5      6
	           / \    / \
	          9   7  8   10
	         / \
	        16  18 

	        */
	var heap_data = [1, 5, 6, 9, 7, 8, 10, 16, 18];
	//Get the size of array
	let n = heap_data.count;
	print(" Min heap : ");
	obj.print_data(heap_data, n);
	obj.max_heap(&heap_data, n);
	print(" Max heap : ");
	obj.print_data(heap_data, n);
}
main();

Output

 Min heap :
  1  5  6  9  7  8  10  16  18
 Max heap :
  18  16  10  9  7  8  6  5  1


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







© 2021, kalkicode.com, All rights reserved