Question

Java language

1. Sort any 10 keys using Min Heap.

2. Sort any 10 keys using Max Heap.

Answer 1

1) Implementation of Heap Sort using MIN heap

import java.io.*;

class GFG {
   static void heapify(int arr[], int n, int i)
   {
       int smallest = i;
       int l = 2 * i + 1;  
       int r = 2 * i + 2;

if (l < n && arr[l] < arr[smallest])
           smallest = l;

if (r < n && arr[r] < arr[smallest])
           smallest = r;
       if (smallest != i) {
           int temp = arr[i];
           arr[i] = arr[smallest];
           arr[smallest] = temp;  
           heapify(arr, n, smallest);
       }
   }
   static void heapSort(int arr[], int n)
   {
       for (int i = n / 2 - 1; i >= 0; i--)
           heapify(arr, n, i);
       for (int i = n - 1; i >= 0; i--) {
          
           int temp = arr[0];
           arr[0] = arr[i];
           arr[i] = temp;
           heapify(arr, i, 0);
       }
   }

static void printArray(int arr[], int n)
   {
       for (int i = 0; i < n; ++i)
           System.out.print(arr[i] + " ");
       System.out.println();
   }

   // Main program
   public static void main(String[] args)
   {
       int arr[] = { 7,4,8, 6,1, 3, 2, 9,5,10 };
       int n = arr.length;

       heapSort(arr, n);

       System.out.println("Sorted array is ");
       printArray(arr, n);
   }
}
Here, we are implementing min heap algorithm to sort the given keys in descendinng order. Therefore, the output is-

Sorted array is:

10 9 8 7 6 5 4 3 2 1

2) Implementation of Heap sort using MAX HEAP:

public class HeapSort
{
   public void sort(int arr[])
   {
       int n = arr.length;

for (int i = n / 2 - 1; i >= 0; i--)
           heapify(arr, n, i);

for (int i=n-1; i>0; i--)
       {
int temp = arr[0];
           arr[0] = arr[i];
           arr[i] = temp;

heapify(arr, i, 0);
       }
   }
   void heapify(int arr[], int n, int i)
   {
       int largest = i;
       int l = 2*i + 1;
       int r = 2*i + 2;

if (l < n && arr[l] > arr[largest])
           largest = l;

if (r < n && arr[r] > arr[largest])
           largest = r;

if (largest != i)
       {
           int swap = arr[i];
           arr[i] = arr[largest];
           arr[largest] = swap;

heapify(arr, n, largest);
       }
   }

static void printArray(int arr[])
   {
       int n = arr.length;
       for (int i=0; i<n; ++i)
           System.out.print(arr[i]+" ");
       System.out.println();
   }

   // Main program
   public static void main(String args[])
   {
       int arr[] = {12,11,5,1,4,2,9, 6,3,7};
       int n = arr.length;

       HeapSort ob = new HeapSort();
       ob.sort(arr);

       System.out.println("Sorted array is");
       printArray(arr);
   }
}
Here we are implementing the heap sort to sort the keys in ascending order using MAX HEAP. Therefore, the output is-

Sorted array is :

1 , 2 , 3 , 4 , 5 , 6 , 7 , 9 , 11, 12

If you are satisfied by my answer please give a thumbs up. Thank you.