Max heap to min heap conversion
Given a array of integers, which is form of binary max heap. Our goal is to transform this max into a min heap in efficient way. For example.
In above image clear indicates swapping the node value. Note that there is possible you are logic are based on different calculation. But converted resultant tree should be form of min heap. (conclusion resultantant tree can be more than one form are possible but those will follow the min heap properties).
Here given code implementation process.
//C Program
//Max heap to min 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 min 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_in = compare(arr, left, right, root, size);
if(next_in != -1)
{
heap(arr,size,next_in);
}
}
//Display array elements
void print_data(int arr[],int size)
{
for(int i = 0; i < size; i++)
{
printf("%3d",arr[i] );
}
printf("\n");
}
void min_heap(int arr[],int size)
{
for (int i = (size/2)-1; i >= 0; i--)
{
heap(arr,size,i);
}
}
int main()
{
/*
10
/ \
9 8
/ \ / \
5 7 1 6
/
4
*/
//Collection of max heap elements
int heap[] = { 10, 9, 8, 5, 7, 1, 6, 4};
//Get the size of elements
int n = sizeof(heap) / sizeof(heap[0]);
printf(" Max heap : \n");
print_data(heap,n);
/*
1
/ \
4 6
/ \ / \
5 7 8 10
/
9
*/
min_heap(heap,n);
printf(" Min heap : \n");
print_data(heap,n);
return 0;
}
Output
Max heap :
10 9 8 5 7 1 6 4
Min heap :
1 4 6 5 7 8 10 9/*
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 min 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_in = this->compare(arr, left, right, root, size);
if (next_in != -1) {
this->heap(arr, size, next_in);
}
}
//Display array elements
void print_data(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
cout << "\n";
}
void min_heap(int arr[], int size) {
for (int i = (size / 2) - 1; i >= 0; i--) {
this->heap(arr, size, i);
}
}
};
int main() {
MyHeap obj = MyHeap();
/*
10
/ \
9 8
/ \ / \
5 7 1 6
/
4
*/
//Collection of max heap elements
int heap_data[] = {
10,
9,
8,
5,
7,
1,
6,
4
};
//Get the size of elements
int n = sizeof(heap_data) / sizeof(heap_data[0]);
cout << " Max heap : \n";
obj.print_data(heap_data, n);
/*
1
/ \
4 6
/ \ / \
5 7 8 10
/
9
*/
obj.min_heap(heap_data, n);
cout << " Min heap : \n";
obj.print_data(heap_data, n);
return 0;
}
Output
Max heap :
10 9 8 5 7 1 6 4
Min heap :
1 4 6 5 7 8 10 9/*
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 min 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_in = compare(arr, left, right, root, size);
if(next_in != -1)
{
heap(arr,size,next_in);
}
}
//Display 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 min_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();
/*
10
/ \
9 8
/ \ / \
5 7 1 6
/
4
*/
//Collection of max heap elements
int heap_data[] = { 10, 9, 8, 5, 7, 1, 6, 4};
//Get the size of elements
int n = heap_data.length;
System.out.print(" Max heap : \n");
obj.print_data(heap_data,n);
/*
1
/ \
4 6
/ \ / \
5 7 8 10
/
9
*/
obj.min_heap(heap_data,n);
System.out.print(" Min heap : \n");
obj.print_data(heap_data,n);
}
}
Output
Max heap :
10 9 8 5 7 1 6 4
Min heap :
1 4 6 5 7 8 10 9/*
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 min 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_in = compare(arr, left, right, root, size);
if (next_in != -1) {
heap(arr, size, next_in);
}
}
//Display 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 min_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();
/*
10
/ \
9 8
/ \ / \
5 7 1 6
/
4
*/
//Collection of max heap elements
int []heap_data = {
10,
9,
8,
5,
7,
1,
6,
4
};
//Get the size of elements
int n = heap_data.Length;
Console.Write(" Max heap : \n");
obj.print_data(heap_data, n);
obj.min_heap(heap_data, n);
Console.Write(" Min heap : \n");
obj.print_data(heap_data, n);
}
}
Output
Max heap :
10 9 8 5 7 1 6 4
Min heap :
1 4 6 5 7 8 10 9<?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 min 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_in = $this->compare($arr, $left, $right, $root, $size);
if ($next_in != -1) {
$this->heap($arr, $size, $next_in);
}
}
//Display array elements
public function print_data($arr, $size) {
for ($i = 0; $i < $size; $i++) {
echo(" ". $arr[$i]);
}
echo("\n");
}
public function min_heap(&$arr, $size) {
for ($i = (intval($size / 2)) - 1; $i >= 0; $i--) {
$this->heap($arr, $size, $i);
}
}
}
function main() {
$obj = new MyHeap();
/*
10
/ \
9 8
/ \ / \
5 7 1 6
/
4
*/
//Collection of max heap elements
$heap_data = array(10, 9, 8, 5, 7, 1, 6, 4);
//Get the size of elements
$n = count($heap_data);
echo(" Max heap : \n");
$obj->print_data($heap_data, $n);
/*
1
/ \
4 6
/ \ / \
5 7 8 10
/
9
*/
$obj->min_heap($heap_data, $n);
echo(" Min heap : \n");
$obj->print_data($heap_data, $n);
}
main();
Output
Max heap :
10 9 8 5 7 1 6 4
Min heap :
1 4 6 5 7 8 10 9/*
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 min 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_in = this.compare(arr, left, right, root, size);
if (next_in != -1) {
this.heap(arr, size, next_in);
}
}
//Display array elements
print_data(arr, size) {
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
min_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();
/*
10
/ \
9 8
/ \ / \
5 7 1 6
/
4
*/
//Collection of max heap elements
var heap_data = [10, 9, 8, 5, 7, 1, 6, 4];
//Get the size of elements
var n = heap_data.length;
process.stdout.write(" Max heap : \n");
obj.print_data(heap_data, n);
/*
1
/ \
4 6
/ \ / \
5 7 8 10
/
9
*/
obj.min_heap(heap_data, n);
process.stdout.write(" Min heap : \n");
obj.print_data(heap_data, n);
}
main();
Output
Max heap :
10 9 8 5 7 1 6 4
Min heap :
1 4 6 5 7 8 10 9# 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 min 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_in = self.compare(arr, left, right, root, size)
if (next_in != -1) :
self.heap(arr, size, next_in)
# Display array elements
def print_data(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
def min_heap(self, arr, size) :
i = (int(size / 2)) - 1
while (i >= 0) :
self.heap(arr, size, i)
i -= 1
def main() :
obj = MyHeap() # Collection of max heap elements
#
# 10
# / \
# 9 8
# / \ / \
# 5 7 1 6
# /
# 4
#
# Collection of max heap elements
heap_data = [10, 9, 8, 5, 7, 1, 6, 4] # Get the size of elements
n = len(heap_data)
print(" Max heap : \n", end = "")
obj.print_data(heap_data, n)
#
# 1
# / \
# 4 6
# / \ / \
# 5 7 8 10
# /
# 9
#
obj.min_heap(heap_data, n)
print(" Min heap : \n", end = "")
obj.print_data(heap_data, n)
if __name__ == "__main__":
main()
Output
Max heap :
10 9 8 5 7 1 6 4
Min heap :
1 4 6 5 7 8 10 9# 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 min 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
# Display array elements
def print_data(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
def min_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()
#
# 10
# / \
# 9 8
# / \ / \
# 5 7 1 6
# /
# 4
#
# Collection of max heap elements
heap_data = [10, 9, 8, 5, 7, 1, 6, 4]
# Get the size of elements
n = heap_data.length
print(" Max heap :\n")
obj.print_data(heap_data, n)
#
# 1
# / \
# 4 6
# / \ / \
# 5 7 8 10
# /
# 9
#
obj.min_heap(heap_data, n)
print(" Min heap :\n")
obj.print_data(heap_data, n)
end
main()
Output
Max heap :
10 9 8 5 7 1 6 4
Min heap :
1 4 6 5 7 8 10 9
/*
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 min 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_in: Int = this.compare(arr, left, right, root, size);
if (next_in != -1) {
this.heap(arr, size, next_in);
}
}
//Display 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 min_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();
/*
10
/ \
9 8
/ \ / \
5 7 1 6
/
4
*/
//Collection of max heap elements
var heap_data: Array[Int] = Array(10, 9, 8, 5, 7, 1, 6, 4);
//Get the size of elements
val n: Int = heap_data.length;
print(" Max heap : \n");
obj.print_data(heap_data, n);
/*
1
/ \
4 6
/ \ / \
5 7 8 10
/
9
*/
obj.min_heap(heap_data, n);
print(" Min heap : \n");
obj.print_data(heap_data, n);
}
}
Output
Max heap :
10 9 8 5 7 1 6 4
Min heap :
1 4 6 5 7 8 10 9/*
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 min 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_in = self.compare(&arr, left, right, root, size);
if (next_in != -1) {
self.heap(&arr, size, next_in);
}
}
//Display 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 min_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();
/*
10
/ \
9 8
/ \ / \
5 7 1 6
/
4
*/
//Collection of max heap elements
var heap_data = [10, 9, 8, 5, 7, 1, 6, 4];
//Get the size of elements
let n = heap_data.count;
print(" Max heap : \n", terminator: "");
obj.print_data(heap_data, n);
/*
1
/ \
4 6
/ \ / \
5 7 8 10
/
9
*/
obj.min_heap(&heap_data, n);
print(" Min heap : \n", terminator: "");
obj.print_data(heap_data, n);
}
main();
Output
Max heap :
10 9 8 5 7 1 6 4
Min heap :
1 4 6 5 7 8 10 9
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