Posted on by Kalkicode
Code Heap

# Implement max heap using array

Here given code implementation process.

//C Program
//Implement max heap using array
#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;
}

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_step = compare(arr, left, right, root, size);

if(next_step != -1)
{
heap(arr,size,next_step);
}
}
//Show array elements
void print_data(int arr[],int size)
{
printf("\n");
for(int i = 0; i < size; i++)
{
printf("%3d",arr[i] );
}
}
void max_heap(int arr[],int size)
{

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

{
//Array elements
int arr[] = {4, 7, 8, 2, 9, 3, 1, 6, 10};

/*

initial elements

4
/      \
/        \
7          8
/   \       /  \
2     9     3    1
/ \
6   10
*/
//find the length of array elements
int size = sizeof(arr)/sizeof(arr[0]);

printf("\n Before elements ");
//Display array elements
print_data(arr,size);

max_heap(arr,size);

/*
After convert into max heap elements

10
/      \
/        \
9          8
/   \       /  \
7    4      3    1
/ \
6   2
*/

printf("\n After Max heap elements ");
//Display array elements
print_data(arr,size);

printf("\n");
return 0;
}

#### Output

Before elements
4  7  8  2  9  3  1  6 10
After Max heap elements
10  9  8  7  4  3  1  6  2
/*
C++ Program
Implement max heap using array
*/

#include<iostream>

using namespace std;
class MaxHeap {
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_step = this->compare(arr, left, right, root, size);
if (next_step != -1) {
this->heap(arr, size, next_step);
}
}
void print_data(int arr[], int size) {
cout << "\n";
int i = 0;
while (i < size) {
cout << "   " << arr[i];
i++;
}
}
void max_heap(int arr[], int size) {
int i = (size / 2) - 1;
while (i >= 0) {
this->heap(arr, size, i);
i--;
}
}
};
int main() {
MaxHeap obj;
int arr[] = {
4,
7,
8,
2,
9,
3,
1,
6,
10
};
/*

initial elements

4
/      \
/        \
7          8
/   \       /  \
2     9     3    1
/ \
6   10
*/
int size = sizeof(arr)/sizeof(arr[0]);
cout << "\n Before elements ";
obj.print_data(arr, size);

obj.max_heap(arr, size);
/*
After convert into max heap elements

10
/      \
/        \
9          8
/   \       /  \
7    4      3    1
/ \
6   2
*/

cout << "\n After Max heap elements ";
obj.print_data(arr, size);
return 0;
}

#### Output

Before elements
4   7   8   2   9   3   1   6   10
After Max heap elements
10   9   8   7   4   3   1   6   2
/*
Java program
Implement max heap using array
*/

public class MaxHeap {
//swap array element
public void swap(int []arr, int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
//compare node value
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_step = compare(arr, left, right, root, size);

if (next_step != -1) {
heap(arr, size, next_step);
}
}
public void print_data(int []arr, int size) {

System.out.print("\n");

int i = 0;

while ( i < size) {

System.out.print("   "+ arr[i]);

i++;
}
}
public void max_heap(int []arr, int size) {
int i = (size/2) - 1;
while ( i >= 0) {
heap(arr, size, i);
i--;
}
}

public static void main(String[] args) {

MaxHeap obj = new MaxHeap();

//Array elements
int []arr = {4, 7, 8, 2, 9, 3, 1, 6, 10};

/*

initial elements

4
/      \
/        \
7          8
/   \       /  \
2     9     3    1
/ \
6   10
*/
//find the length of array elements
int size = arr.length;

System.out.print("\n Before elements ");
//Display array elements
obj.print_data(arr,size);

obj.max_heap(arr,size);

/*
After convert into max heap elements

10
/      \
/        \
9          8
/   \       /  \
7    4      3    1
/ \
6   2
*/

System.out.print("\n After Max heap elements ");
//Display array elements
obj.print_data(arr,size);

}
}

#### Output

Before elements
4   7   8   2   9   3   1   6   10
After Max heap elements
10   9   8   7   4   3   1   6   2
/*
C# program
Implement max heap using array
*/

using System;
public class MaxHeap {
//swap array element
public void swap(int []arr, int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
//compare node value
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_step = compare(arr, left, right, root, size);

if (next_step != -1) {
heap(arr, size, next_step);
}
}
public void print_data(int []arr, int size) {

Console.Write("\n");

int i = 0;

while ( i < size) {

Console.Write("   "+ arr[i]);

i++;
}
}
public void max_heap(int []arr, int size) {
int i = (size/2) - 1;
while ( i >= 0) {
heap(arr, size, i);
i--;
}
}

public static void Main(String[] args) {

MaxHeap obj = new MaxHeap();

//Array elements
int []arr = {4, 7, 8, 2, 9, 3, 1, 6, 10};

/*

initial elements

4
/      \
/        \
7          8
/   \       /  \
2     9     3    1
/ \
6   10
*/
//find the.Length of array elements
int size = arr.Length;

Console.Write("\n Before elements ");
//Display array elements
obj.print_data(arr,size);

obj.max_heap(arr,size);

/*
After convert into max heap elements

10
/      \
/        \
9          8
/   \       /  \
7    4      3    1
/ \
6   2
*/

Console.Write("\n After Max heap elements ");
//Display array elements
obj.print_data(arr,size);

}
}

#### Output

Before elements
4   7   8   2   9   3   1   6   10
After Max heap elements
10   9   8   7   4   3   1   6   2
# Python 3 Program
# Implement max heap using array

class MaxHeap :
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_step = self.compare(arr, left, right, root, size)
if (next_step != -1) :
self.heap(arr, size, next_step)

def print_data(self, arr, size) :

i = 0
while (i < size) :
print("  ", arr[i],end="")
i += 1

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

def main() :
obj = MaxHeap()
arr = [4, 7, 8, 2, 9, 3, 1, 6, 10]

#
#    initial elements
#              4
#           /      \
#          /        \
#         7          8
#       /   \       /  \
#      2     9     3    1
#     / \
#    6   10
#
size = len(arr)
print("\n Before elements ")
obj.print_data(arr, size)
obj.max_heap(arr, size)
#
#    After convert into max heap elements
#              10
#           /      \
#          /        \
#         9          8
#       /   \       /  \
#      7    4      3    1
#     / \
#    6   2
#
print("\n After Max heap elements ")
obj.print_data(arr, size)

if __name__ == "__main__":
main()

#### Output

Before elements
4   7   8   2   9   3   1   6   10
After Max heap elements
10   9   8   7   4   3   1   6   2
# Ruby Program
# Implement max heap using array

class MaxHeap
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_step = self.compare(arr, left, right, root, size)
if (next_step != -1)
self.heap(arr, size, next_step)
end
end
def print_data(arr, size)
print("\n")
i = 0
while (i < size)
print("   ", arr[i])
i += 1
end
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 = MaxHeap.new()
arr = [4, 7, 8, 2, 9, 3, 1, 6, 10]

#
#    initial elements
#              4
#           /      \
#          /        \
#         7          8
#       /   \       /  \
#      2     9     3    1
#     / \
#    6   10
#
size = arr.length
print("\n Before elements ")
obj.print_data(arr, size)
obj.max_heap(arr, size)
#
#    After convert into max heap elements
#              10
#           /      \
#          /        \
#         9          8
#       /   \       /  \
#      7    4      3    1
#     / \
#    6   2
#
print("\n After Max heap elements ")
obj.print_data(arr, size)
end
main()

#### Output

Before elements
4   7   8   2   9   3   1   6   10
After Max heap elements
10   9   8   7   4   3   1   6   2
<?php
/*
Php Program
Implement max heap using array
*/

class MaxHeap {
public  function swap(&\$arr, \$first, \$second) {
\$auxiliary = \$arr[\$first];
\$arr[\$first] = \$arr[\$second];
\$arr[\$second] = \$auxiliary;
}
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_step = \$this->compare(\$arr, \$left, \$right, \$root, \$size);
if (\$next_step != -1) {
\$this->heap(\$arr, \$size, \$next_step);
}
}
public  function print_data(\$arr, \$size) {
echo("\n");
\$i = 0;
while (\$i < \$size) {
echo("   ". \$arr[\$i]);
\$i++;
}
}
public  function max_heap(&\$arr, \$size) {
\$i = intval(\$size / 2) - 1;
while (\$i >= 0) {
\$this->heap(\$arr, \$size, \$i);
\$i--;
}
}
}

function main() {
\$obj = new MaxHeap();
\$arr = array(4, 7, 8, 2, 9, 3, 1, 6, 10);
/*

initial elements

4
/      \
/        \
7          8
/   \       /  \
2     9     3    1
/ \
6   10
*/
\$size = count(\$arr);
echo("\n Before elements ");
\$obj->print_data(\$arr, \$size);
\$obj->max_heap(\$arr, \$size);
/*
After convert into max heap elements

10
/      \
/        \
9          8
/   \       /  \
7    4      3    1
/ \
6   2
*/

echo("\n After Max heap elements ");
\$obj->print_data(\$arr, \$size);
}
main();

#### Output

Before elements
4   7   8   2   9   3   1   6   10
After Max heap elements
10   9   8   7   4   3   1   6   2
/*
Node Js Program
Implement max heap using array
*/

class MaxHeap {
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_step = this.compare(arr, left, right, root, size);
if (next_step != -1) {
this.heap(arr, size, next_step);
}
}
print_data(arr, size) {
process.stdout.write("\n");
var i = 0;
while (i < size) {
process.stdout.write("   " + arr[i]);
i++;
}
}
max_heap(arr, size) {
var i = parseInt(size / 2) - 1;
while (i >= 0) {
this.heap(arr, size, i);
i--;
}
}
}

function main() {
var obj = new MaxHeap();
var arr = [4, 7, 8, 2, 9, 3, 1, 6, 10];
/*

initial elements

4
/      \
/        \
7          8
/   \       /  \
2     9     3    1
/ \
6   10
*/
var size = arr.length;
process.stdout.write("\n Before elements ");
obj.print_data(arr, size);
obj.max_heap(arr, size);
/*
After convert into max heap elements

10
/      \
/        \
9          8
/   \       /  \
7    4      3    1
/ \
6   2
*/

process.stdout.write("\n After Max heap elements ");
obj.print_data(arr, size);
}

main();

#### Output

Before elements
4   7   8   2   9   3   1   6   10
After Max heap elements
10   9   8   7   4   3   1   6   2
/*
Swift 4 Program
Implement max heap using array
*/

class MaxHeap {
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_step: Int = self.compare(&arr, left, right, root, size);
if (next_step != -1) {
self.heap(&arr, size, next_step);
}
}
func print_data(_ arr: [Int] , _ size : Int) {

var i: Int = 0;
while (i < size) {
print("  ", arr[i],terminator:"");
i += 1;
}
}
func max_heap(_ 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: MaxHeap = MaxHeap();
var arr: [Int] = [4, 7, 8, 2, 9, 3, 1, 6, 10];
/*

initial elements

4
/      \
/        \
7          8
/   \       /  \
2     9     3    1
/ \
6   10
*/
let size: Int = arr.count;
print("\n Before elements ");
obj.print_data(arr, size);
obj.max_heap(&arr, size);
/*
After convert into max heap elements

10
/      \
/        \
9          8
/   \       /  \
7    4      3    1
/ \
6   2
*/

print("\n After Max heap elements ");
obj.print_data(arr, size);
}
main();

#### Output

Before elements
4   7   8   2   9   3   1   6   10
After Max heap elements
10   9   8   7   4   3   1   6   2

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

Categories
Relative Post