Constructing a max heap using java

In this post, we will learn about max heap trees and how to create max heap tree in Java.

Definition of a max heap tree:

In a max heap tree, the root of the tree has the maximum element. It is a binary tree where the parent node should have a greater value than its two child nodes.

Mapping of elements of a tree is with the help of an array so if we have position i, then 2*i+1 is the left child of the parent node at i and 2*i+2 is the right child. The parent node will be at arr[0];

Thus to access the nodes:
PARENT NODE:arr[(i-1)/2]
LEFT CHILD NODE:arr[(2*i+1)]
RIGHT CHILD NODE:arr[(2*i+2)];



Java program to create a max heap tree:

import java.util.Scanner;
public class maxheap{
public static void heapify(int[] a,int i,int n)
{
int t;
int lc=2*i+1;
int rc=2*i+2;
int max=i;
if(lc<n && a[max]<a[lc])
{
max=lc;
}
if(rc<n &&a[max]<a[rc])
{
max=rc;
}
if(max!=i)
{
t=a[i];
a[i]=a[max];
a[max]=t;
heapify(a,max,n);
}
}
public static void buildheap(int[] a,int n)
{
for(int i=n/2;i>=0;i--)
{
heapify(a,0,n);
}
}
public static void main(String args[])
{
int n;
int[] a=new int[10];
System.out.println("enter the number of elements");
n=STDIN_SCANNER.nextInt();
System.out.println("enter the array");
for(int i=0;i<n;i++)
{
a[i]=STDIN_SCANNER.nextInt();
}
buildheap(a,n);
System.out.print("the heap is \n");
for(int i=0;i<n/2;i++)
{
System.out.print("parent "+a[i]+"\t"+"left_child "+a[(2*i+1)]+"\t"+"right_child "+a[(2*i+2)]);
System.out.println();
}
}
public final static Scanner STDIN_SCANNER=new Scanner(System.in);
}
output:
enter the number of elements
5
enter the array
1
6
4
8
9
the heap is
parent 9        left_child 8    right_child 4
parent 8        left_child 6    right_child 1

 

In this program, we can see that we are trying to build a max heap tree. So we have taken two variables lc and rc that will contain the left and right child respectively. Now, initialize max as i and comparing max with the left as well as the right child. If lc or rc is greater than max initializes itself with lc or  rc respectively. In the buildheap () function we call this heapify()  function to build the respective max heap. So from the main function call the buildheap () and print its parent, left_child, and right_child respectively.

Also, learn,

Leave a Reply

Your email address will not be published. Required fields are marked *