Question

•Make the steps of the followed the numbers 34, 15, 23, 9, 41, 26, 39, 11, 7, 28 by using Heap Sort!

Answer 1

The following is the code for above question. In this code, the array will be displayed for each step of heap sort.

public class Main {
    public static int count=0;
    public static void main(String args[]) {
      int elements[] = {9,5,2,12,7,4};
      int n=elements.length,i,temp;
      for(i=n/2-1;i>=0;i--) 
      { //building the max heap
        heapify(elements,n,i);
      }

     for(i=n-1;i>=0;i--) 
     {                     //Heap sort starts
      temp=elements[0];
      elements[0]=elements[i];
      elements[i]=temp;

                               // Heapify root element
      heapify(elements,i,0);
     }
      
        System.out.print("Now the array is sorted");
      
    }
    
      public static void heapify(int elements[], int n, int i) {
      // we have to find the largest among root, left and right child
      int largest=i,l=2*i+1,r=2*i+2,temp;
  
      if(l<n&&elements[l]>elements[largest])
      {
        largest=l;
      }
  
      if(r<n&&elements[r]>elements[largest])
      {
        largest=r;
      }
      if(largest!=i) {  // If root is not largest then swap and continue;
        temp=elements[i];
        elements[i]=elements[largest];
        elements[largest]=temp;
  
        heapify(elements,n,largest);
      }
      count++;
      System.out.printf("Step %d-> ",count);
      for(i=0;i<elements.length;++i)
      {
        System.out.print(elements[i]+" ");
      }
      System.out.println("\n");
    }
  }
  

I am also attaching the output for your reference.

Output:

Step 1-> 9 5 4 12 7 2

Step 2-> 9 5 4 12 7 2

Step 3-> 9 12 4 5 7 2

Step 4-> 9 12 4 5 7 2

Step 5-> 12 9 4 5 7 2

Step 6-> 12 9 4 5 7 2

Step 7-> 9 7 4 5 2 12

Step 8-> 9 7 4 5 2 12

Step 9-> 9 7 4 5 2 12

Step 10-> 7 5 4 2 9 12

Step 11-> 7 5 4 2 9 12

Step 12-> 7 5 4 2 9 12

Step 13-> 5 2 4 7 9 12

Step 14-> 5 2 4 7 9 12

Step 15-> 4 2 5 7 9 12

Step 16-> 2 4 5 7 9 12

Step 17-> 2 4 5 7 9 12

Now the array is sorted

#Please dont forget to upvote if you find the solution helpful. Feel free to ask doubts if any, in the comments section. Thank you.