Heap Sort for decreasing order using min heap in Java

In this tutorial, we are going to find the given numbers or nodes in descending order using Heap Sort using Java (core) language. We will see an easy program to print the numbers from the biggest to the smallest using the given requirements.

You can also learn:

• How to Implement Heap Sort using Java

How to display given heap in decreasing order in Java using Heap sort

1. In the following program, we first created the class named ‘Prac’ and inside that class, we created a method named ‘heapy’. And passed parameters to it. In the method heapy we analyzed three variables to find the smallest node, right node, left node and the root node.
2. The next part is the conditional part where we have applied conditions using the if statement. Also, we calculated the sub-tree and stored the sub-tree elements in the class heapy itself.

   class Prac
   {
     static void heapy(int arr[],int n,int i)
     {
       int small=i;
       int a=2*i+1;
       int b=2*i+2;
       
       if(a<n && arr[a]<arr[small])
         small=a;
       if(b<n && arr[b]<arr[small])
         small=b;
       if(small!=i)
       {
         int temp=arr[i];
         arr[i]=arr[small];
         arr[small]=temp;
         heapy(arr,n,small);
       }
     }

    

3. In this part, we also created a new Method named ‘sort’ and using for loop here we get another sub-tree which has the smallest node, right node, left node as well as the root node. So, by combining the two methods and applying the conditions we get the final tree.
4. We found out the final list of the elements that are stored in the Array list.

5. static void sort(int n,int arr[])
     {
       for(int i=n/2-1;i<=0;i--)
       heapy(arr,n,i);
       
       for(int i=n-1;i>=0;i--)
       {
         int temp = arr[0]; 
         arr[0] = arr[i]; 
         arr[i] = temp;
         heapy(arr,i,0);
       }
     }

    

6. Here to print the elements of the tree we created another method named ‘print’ and passed parameters to it. Here we also declared the main method and in it, we provided the array of elements that we need to sort from descending order to ascending order. And then finally we get the output.

7.   public static void main(String[] args) 
     { 
       int arr[] = { 34,67,89,23,45,10 }; 
       int n = arr.length; 
   
       heapy(arr, n); 
   
       System.out.println("Sorted array is "); 
       print(arr, n); 
     } 
   }

    

8. Output of the program:

Sorted array is 
89 67 45 34 23 10 

 

Program:

Below is our program for the task in Java:

class Prac
{
  static void heapy(int arr[],int n,int i)
  {
    int small=i;
    int a=2*i+1;
    int b=2*i+2;
    
    if(a<n && arr[a]<arr[small])
      small=a;
    if(b<n && arr[b]<arr[small])
      small=b;
    if(small!=i)
    {
      int temp=arr[i];
      arr[i]=arr[small];
      arr[small]=temp;
      heapy(arr,n,small);
    }
  }
  static void sort(int n,int arr[]) {
    for(int i=n/2-1;i<=0;i--)
      heapy(arr,n,i); 
    for(int i=n-1;i>=0;i--) {	  
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;
      heapy(arr,i,0);
    }
  }
  static void print(int arr[], int n) 
  { 
    for (int i = 0; i < n; ++i) 
      System.out.print(arr[i] + " "); 
    System.out.println(); 
  } 
  public static void main(String[] args) 
  { 
    int arr[] = { 34,67,89,23,45,10 }; 
    int n = arr.length; 

    heapy(arr, n); 

    System.out.println("Sorted array is "); 
    print(arr, n); 
  } 
}