Implement algorithm HeapSortA Create an array A of size 100

Implement algorithm HeapSort(A). Create an array A of size 100 containing random integers between 1 and 500. Call HeapSort(A). Output the resulting array.

Solution

Note:

1. Sort the elements in Ascending order go for Max-heap OR for Decending order go for Min-heap

2. What is Max-heap ? --> Largest element must be root

3. Knowing the heapify ? --> After removing root element, re-arranging the tree or array satisfying Max-haep or

Min-heap rules

4. Heapify: The process of making changes to tree so that it satisfies max-heap or min-heap property

HeapSort Algorithm:

Step 1: Declare an array A[n] and assign random intergers from 1 to 500 using random function or method

Step 2: Heapify an array A[n]

Step 3: Swap the root and last element of an array

Step 4: Remove the last element of an array and store in new array from last index to first index

Step 5: Repeat STEP 2 untill size of an array is 1

Simple Program in Java:

import java.util.Random;

public class HeapSort {

   public static void main(String[] args) {
   int[] array = new int[100];
  
   Random ran = new Random();
   for( int i=0; i < 100; i++)
       array[i] = ran.nextInt(500) + 1 ;
  
   System.out.println(\"Before sort: \");
   for (int i= 0; i< 100; i++) {
          if( i%20 == 0)
              System.out.println();
          System.out.print(array[i] + \" \");
       }
   new HeapSort().sort(array);
  
   System.out.println(\"\ After sort: \");
   for (int i= 0; i< 100; i++) {
      if( i%20 == 0)
          System.out.println();
      System.out.print(array[i] + \" \");
   }
   }

   public void sort(int data[]) {
   int size = data.length;
  
   for (int i = size / 2 - 1; i >= 0; i--) {
   heapify(i, data, size);
   }

   for(int i=data.length-1;i>=0;i--){
   int temp = data[0];
   data[0]=data[i];
   data[i]=temp;

   //reduce the heap window by 1
   size = size-1;

   //call max heapify on the reduced heap
   heapify(0, data, size);
   }
   }

   private int leftChild(int i){
   return 2 * i + 1;
   }
   private int rightChild(int i) {
   return 2 * i + 2;
   }

   private void heapify(int i, int[] data, int size) {
   int largestElementIndex = i;

   int leftChildIndex = leftChild(i);
   if (leftChildIndex < size && data[leftChildIndex] > data[largestElementIndex]) {
   largestElementIndex = leftChildIndex;
   }

   int rightChildIndex = rightChild(i);
   if (rightChildIndex < size && data[rightChildIndex] > data[largestElementIndex]) {
   largestElementIndex = rightChildIndex;
   }

   if (largestElementIndex != i) {
   int swap = data[i];
   data[i] = data[largestElementIndex];
   data[largestElementIndex] = swap;

   // Recursively heapify the affected sub-tree
   heapify(largestElementIndex, data, size);
   }
   }

   }