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
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