Skip to main content

Heap sort in decreasing order using min heap

Here given code implementation process.

//C Program
//Heap sort in decreasing order using min heap
#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;
}
//Min heap comparison
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;
}
//Control heap operations
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 print_data(int arr[],int size)
{

  for(int i = 0; i < size; i++)
  {
    printf("%3d",arr[i] );
  }
    printf("\n");
}
//Perform heap sort by using the min heap
//Note that here smallest element are swap to end of array, 
//Which are calculated by min heap
void heap_sort(int arr[],int size)
{
  
  for (int i = (size/2)-1; i >= 0; i--)
  {
    heap(arr,size,i);
  }
  for (int i = size-1; i >= 0; i--)
  {
    //Shift the smallest element to last position
    swap(arr, 0, i);
    heap(arr, i, 0);
  }
}
int main()
{
  //Define collection of array elements
  int arr[] = { 7, 6, -7, 1, 3, 8, 21, 11,5,0, 12 ,5};
  //Get the size of array elements
  int size = sizeof(arr)/sizeof(arr[0]);
  printf("  Before Sort \n");
  print_data(arr,size);
  heap_sort(arr,size);
  printf("  After Sort \n");
  print_data(arr,size);
  return 0;
}

Output

  Before Sort
  7  6 -7  1  3  8 21 11  5  0 12  5
  After Sort
 21 12 11  8  7  6  5  5  3  1  0 -7
/*
  C++ Program
  Heap sort in decreasing order using min heap
*/
#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;
    }
	//Min heap comparison
	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;
	}
	//Control heap operations
	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 print_data(int arr[], int size) {
		for (int i = 0; i < size; i++) {
			cout << " " << arr[i];
		}
		cout << "\n";
	}
	//Perform heap sort by using the min heap
	//Note that here smallest element are swap to end of array, 
	//Which are calculated by min heap
	void heap_sort(int arr[], int size) {
		for (int i = (size / 2) - 1; i >= 0; i--) {
			this->heap(arr, size, i);
		}
		for (int i = size - 1; i >= 0; i--) {
			//Shift the smallest element to last position
			this->swap(arr, 0, i);
			this->heap(arr, i, 0);
		}
	}
};
int main() {
	MyHeap obj = MyHeap();
	int arr[] = {
		7,
		6,
		-7,
		1,
		3,
		8,
		21,
		11,
		5,
		0,
		12,
		5
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << " Before Sort \n";
	obj.print_data(arr, size);
	obj.heap_sort(arr, size);
	cout << " After Sort \n";
	obj.print_data(arr, size);
	return 0;
}

Output

 Before Sort
 7 6 -7 1 3 8 21 11 5 0 12 5
 After Sort
 21 12 11 8 7 6 5 5 3 1 0 -7
/*
  Java Program
  Heap sort in decreasing order using min heap
*/
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;
  }
  //Min heap comparison
  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;
  }
  //Control heap operations
  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);
    }
  }
  public void print_data(int []arr,int size)
  {
    
    for(int i = 0; i < size; i++)
    {
      System.out.print("  "+arr[i] );

    }
    System.out.print("\n");
  }
  //Perform heap sort by using the min heap
  //Note that here smallest element are swap to end of array, 
  //Which are calculated by min heap
  public void heap_sort(int []arr,int size)
  {
    
    for (int i = (size/2)-1; i >= 0; i--)
    {
      heap(arr,size,i);
    }
    for (int i = size-1; i >= 0; i--)
    {
      //Shift the smallest element to last position
      swap(arr, 0, i);
      heap(arr, i, 0);
    }
  }
  
  public static void main(String[] args) {
    
    MyHeap obj = new MyHeap();
      
    //Define Collection of integer values
    int []arr =  { 7, 6, -7, 1, 3, 8, 21, 11,5,0, 12 ,5};
    //Get the size of array
    int size = arr.length;
    System.out.print("  Before Sort \n");
    obj.print_data(arr,size);

    obj.heap_sort(arr,size);

    System.out.print("  After Sort \n");
    obj.print_data(arr,size);
  }
}

Output

 Before Sort
 7 6 -7 1 3 8 21 11 5 0 12 5
 After Sort
 21 12 11 8 7 6 5 5 3 1 0 -7
/*
  C# Program
  Heap sort in decreasing order using min heap
*/
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;
	}
	//Min heap comparison
	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;
	}
	//Control heap operations
	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);
		}
	}
	public void print_data(int[] arr, int size) {
		for (int i = 0; i < size; i++) {
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	//Perform heap sort by using the min heap
	//Note that here smallest element are swap to end of array, 
	//Which are calculated by min heap
	public void heap_sort(int[] arr, int size) {
		for (int i = (size / 2) - 1; i >= 0; i--) {
			heap(arr, size, i);
		}
		for (int i = size - 1; i >= 0; i--) {
			swap(arr, 0, i);
			heap(arr, i, 0);
		}
	}
	public static void Main(String[] args) {
		MyHeap obj = new MyHeap();
		int[]
		//Define Collection of integer values
		arr = {
			7,
			6,
			-7,
			1,
			3,
			8,
			21,
			11,
			5,
			0,
			12,
			5
		};
		//Get the size of array
		int size = arr.Length;
		Console.Write(" Before Sort \n");
		obj.print_data(arr, size);
		obj.heap_sort(arr, size);
		Console.Write(" After Sort \n");
		obj.print_data(arr, size);
	}
}

Output

 Before Sort
 7 6 -7 1 3 8 21 11 5 0 12 5
 After Sort
 21 12 11 8 7 6 5 5 3 1 0 -7
<?php
/*
  Php Program
  Heap sort in decreasing order using min heap
*/
class MyHeap {
	//Swap two element in array

	public 	function swap(&$arr, $first, $second) {
		$auxiliary = $arr[$first];
		$arr[$first] = $arr[$second];
		$arr[$second] = $auxiliary;
	}
	//Min heap comparison

	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;
	}
	//Control heap operations

	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);
		}
	}
	public 	function print_data($arr, $size) {
		for ($i = 0; $i < $size; $i++) {
			echo(" ". $arr[$i]);
		}
		echo("\n");
	}
	//Perform heap sort by using the min heap
	//Note that here smallest element are swap to end of array, 
	//Which are calculated by min heap

	public 	function heap_sort(&$arr, $size) {
		for ($i = (intval($size / 2)) - 1; $i >= 0; $i--) {
			$this->heap($arr, $size, $i);
		}
		for ($i = $size - 1; $i >= 0; $i--) {
			//Shift the smallest element to last position
			$this->swap($arr, 0, $i);
			$this->heap($arr, $i, 0);
		}
	}
}

function main() {
	$obj = new MyHeap();
	//Define Collection of integer values
	$arr = array(7, 6, -7, 1, 3, 8, 21, 11, 5, 0, 12, 5);
	//Get the size of array
	$size = count($arr);
	echo(" Before Sort \n");
	$obj->print_data($arr, $size);
	$obj->heap_sort($arr, $size);
	echo(" After Sort \n");
	$obj->print_data($arr, $size);

}
main();

Output

 Before Sort
 7 6 -7 1 3 8 21 11 5 0 12 5
 After Sort
 21 12 11 8 7 6 5 5 3 1 0 -7
/*
  Node Js Program
  Heap sort in decreasing order using min heap
*/
class MyHeap {
	//Swap two element in array
	swap(arr, first, second) {
		var auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}

	//Min heap comparison
	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;
	}

	//Control heap operations
	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_data(arr, size) {
		for (var i = 0; i < size; i++) {
			process.stdout.write(" " + arr[i]);
		}

		process.stdout.write("\n");
	}

	//Perform heap sort by using the min heap
	//Note that here smallest element are swap to end of array, 
	//Which are calculated by min heap
	heap_sort(arr, size) {
		for (var i = (parseInt(size / 2)) - 1; i >= 0; i--) {
			this.heap(arr, size, i);
		}

		for (var i = size - 1; i >= 0; i--) {
			//Shift the smallest element to last position
			this.swap(arr, 0, i);
			this.heap(arr, i, 0);
		}
	}
}

function main(args) {
	var obj = new MyHeap();
	//Define Collection of integer values
	var arr = [7, 6, -7, 1, 3, 8, 21, 11, 5, 0, 12, 5];
	//Get the size of array
	var size = arr.length;
	process.stdout.write(" Before Sort \n");
	obj.print_data(arr, size);
	obj.heap_sort(arr, size);
	process.stdout.write(" After Sort \n");
	obj.print_data(arr, size);
}

main();

Output

 Before Sort
 7 6 -7 1 3 8 21 11 5 0 12 5
 After Sort
 21 12 11 8 7 6 5 5 3 1 0 -7
#  Python 3 Program
#  Heap sort in decreasing order using min heap

class MyHeap :
	# Swap two element in array
	def swap(self, arr, first, second) :
		auxiliary = arr[first]
		arr[first] = arr[second]
		arr[second] = auxiliary
	 # Min heap comparison
	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
	 # Control heap operations
	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 print_data(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	 # Which are calculated by min heap
	# Note that here smallest element are swap to end of array, 
	# Which are calculated by min heap

	# Perform heap sort by using the min heap
	# Which are calculated by min heap
	# Note that here smallest element are swap to end of array, 
	# Which are calculated by min heap


	def heap_sort(self, arr, size) :
		i = (int(size / 2)) - 1
		while (i >= 0) :
			self.heap(arr, size, i)
			i -= 1
		
		i = size - 1
		while (i >= 0) :
			self.swap(arr, 0, i)
			self.heap(arr, i, 0)
			i -= 1
		
	

def main() :
	obj = MyHeap()
	arr = [7, 6, -7, 1, 3, 8, 21, 11, 5, 0, 12, 5]
	size = len(arr)
	print(" Before Sort \n", end = "")
	obj.print_data(arr, size)
	obj.heap_sort(arr, size)
	print(" After Sort \n", end = "")
	obj.print_data(arr, size)


if __name__ == "__main__":
	main()

Output

 Before Sort
  7  6  -7  1  3  8  21  11  5  0  12  5
 After Sort
  21  12  11  8  7  6  5  5  3  1  0  -7
#  Ruby Program
#  Heap sort in decreasing order using min heap

class MyHeap 
	 # Swap two element in array
	def swap(arr, first, second) 
		auxiliary = arr[first]
		arr[first] = arr[second]
		arr[second] = auxiliary
	end
	 # Min heap comparison
	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
	 # Control heap operations
	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
	def print_data(arr, size) 
		i = 0
		while (i < size) 
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	 # Which are calculated by min heap
	 # Note that here smallest element are swap to end of array, 
	 # Which are calculated by min heap
	 # Perform heap sort by using the min heap
	 # Which are calculated by min heap
	 # Note that here smallest element are swap to end of array, 
	 # Which are calculated by min heap
	def heap_sort(arr, size) 
		i = (size / 2) - 1
		while (i >= 0) 
			self.heap(arr, size, i)
			i -= 1
		end
		i = size - 1
		while (i >= 0) 
			self.swap(arr, 0, i)
			self.heap(arr, i, 0)
			i -= 1
		end
	end
end
def main() 
	obj = MyHeap.new()
	arr = [7, 6, -7, 1, 3, 8, 21, 11, 5, 0, 12, 5]
	size = arr.length
	print(" Before Sort \n")
	obj.print_data(arr, size)
	obj.heap_sort(arr, size)
	print(" After Sort \n")
	obj.print_data(arr, size)
end
main()

Output

 Before Sort 
 7 6 -7 1 3 8 21 11 5 0 12 5
 After Sort 
 21 12 11 8 7 6 5 5 3 1 0 -7
/*
  Scala Program
  Heap sort in decreasing order using min heap
*/
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;
	}
	//Min heap comparison
	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;
	}
	//Control heap operations
	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);
		}
	}
	def print_data(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size) {
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	//Perform heap sort by using the min heap
	//Note that here smallest element are swap to end of array, 
	//Which are calculated by min heap
	def heap_sort(arr: Array[Int], size: Int): Unit = {
		var i: Int = ((size / 2).toInt) - 1;
		while (i >= 0) {
			this.heap(arr, size, i);
			i -= 1;
		}
		i = size - 1;
		while (i >= 0) {
			this.swap(arr, 0, i);
			this.heap(arr, i, 0);
			i -= 1;
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MyHeap = new MyHeap();
		var arr: Array[Int] = Array(7, 6, -7, 1, 3, 8, 21, 11, 5, 0, 12, 5);
		val size: Int = arr.length;
		print(" Before Sort \n");
		obj.print_data(arr, size);
		obj.heap_sort(arr, size);
		print(" After Sort \n");
		obj.print_data(arr, size);
	}
}

Output

 Before Sort
 7 6 -7 1 3 8 21 11 5 0 12 5
 After Sort
 21 12 11 8 7 6 5 5 3 1 0 -7
/*
  Swift Program
  Heap sort in decreasing order using min heap
*/
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;
	}
	//Min heap comparison
	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;
	}
	//Control heap operations
	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);
		}
	}
	func print_data(_ arr: [Int], _ size: Int) {
		var i = 0;
		while (i < size) {
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	//Perform heap sort by using the min heap
	//Note that here smallest element are swap to end of array, 
	//Which are calculated by min heap
	func heap_sort(_ arr: inout [Int], _ size: Int) {
		var i = (size / 2) - 1;
		while (i >= 0) {
			self.heap(&arr, size, i);
			i -= 1;
		}
		i = size - 1;
		while (i >= 0) {
			self.swap(&arr, 0, i);
			self.heap(&arr, i, 0);
			i -= 1;
		}
	}
}
func main() {
	let obj = MyHeap();
	var arr = [7, 6, -7, 1, 3, 8, 21, 11, 5, 0, 12, 5];
	let size = arr.count;
	print(" Before Sort ");
	obj.print_data(arr, size);
	obj.heap_sort(&arr, size);
	print(" After Sort ");
	obj.print_data(arr, size);
}
main();

Output

 Before Sort
  7  6  -7  1  3  8  21  11  5  0  12  5
 After Sort
  21  12  11  8  7  6  5  5  3  1  0  -7




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