Building Heap from an array in Java

Hi coders! today we are going to see how to create a heap from an array in Java. First, we have to see what is a heap? A heap is a complete binary tree which satisfies two properties:-

  1. All the levels have the maximum number of nodes except at the last level. In the last level, all nodes start to fill from the left side. There should not be any gap in tree.
  2. The root node must be greater than (max heap) or less than (min heap) or equal to all the child nodes.

There are two types of heaps:

Max heap

In this heap, the root element is greater than all the child nodes and the rule is the same for all the subsequent level nodes. Example of max heap:

10
/    \
9      8
/ \     /  \
5  6   7   4

Min heap

In this heap, the root element is smaller than all the child nodes and the rule is the same for all the subsequent level nodes. Example of min heap:

1
/    \
2      3
/ \     / \
4  5   6   7

How to create a Max heap from an array in Java

Here we gonna create max heap in Java from array.

For example, we have an array of 9 elements

3 10 4 5 6 7 8 9 5

First, we will make a binary tree from array follow these steps:-

  1. The first element of the array will be the root node.
  2. Then the subsequent number will become the left child and the next one will be the right child and the process goes on.

YOu may also learn: How to find level of a node in Binary Tree in Java

The tree will look like this.

3
/    \
10      4
/ \     / \
5  6   7   8
/ \
9    5

Now to make it a max heap, we will follow these steps

  1. Calculate the position of none leaf nodes ie 5 or 10 or 4, by (n/2)-1.
  2. Heapify only these nodes, start with last none leaf node ie 5.
  3. In Heapify we will compare the parent node with its children and if found smaller than child node, we will swap it with the largest value child.
  4. We will recursively Heapify the nodes until the heap becomes a max heap.

Here is code for the max heap from array in Java

import java.util.Scanner;

public class heap_array {


  static void heapify(int array[], int size, int i) 
  { 
    int largest = i;    // Initialize current node as largest 
    int left = 2 * i + 1;   // position of left child in array = 2*i + 1 
    int right = 2 * i + 2;   // position of right child in array = 2*i + 2 

                                             
    if (left < size && array[left] > array[largest])  // If left child is larger than root 
      largest = left; 
    
    if (right < size && array[right] > array[largest]) // If right child is larger than largest so far 
      largest = right; 
  
    if (largest != i) {         // If largest is not root swap it 
      int swap = array[i]; 
      array[i] = array[largest]; 
      array[largest] = swap; 
  
      heapify(array, size, largest); // Recursively heapify the sub-tree 
    } 
  } 

  static void buildHeap(int arr[], int n) 
  { 
    
    int startIdx = (n / 2) - 1; // Index of last non-leaf node 

    for (int i = startIdx; i >= 0; i--) { 
      heapify(arr, n, i); 
    } 
  } 

  
  static void printHeap(int arr[], int n) 
  { 
    System.out.println("Array representation of Heap:"); 

    for (int i = 0; i < n; ++i) 
    System.out.print(arr[i] + " "); 

    System.out.println(); 
  } 

  
  public static void main(String args[]) 
  {   
    Scanner sc=new Scanner(System.in);
    System.out.println("Enter the size of array: ");
    int n = sc.nextInt(); 
    int arr[]=new int[n];
      
    System.out.println("Enter array: ");
    for(int i=0;i<n;i++)
          arr[i] =sc.nextInt();

    buildHeap(arr, n); 

    printHeap(arr, n); 
  } 
} 

Output:

Enter the size of array: 
9
Enter array: 
3 10 4 5 6 7 8 9 5
Array representation of Heap:
10 9 8 5 6 7 4 3 5 

Final Max heap :
10
/    \
9      8
/ \     / \
5  6   7   4
/  \
3   5

Similarly, for the min heap, we will recursively swap the elements till all the lower elements are higher than the root node. In step 3 we will check for smaller child node than root instead of large child value like in max heap.

Leave a Reply

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