Question

In: Computer Science

Java language 1. Sort any 10 keys using Min Heap. 2. Sort any 10 keys using...

Java language

1. Sort any 10 keys using Min Heap.

2. Sort any 10 keys using Max Heap.

Solutions

Expert Solution

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.


Related Solutions

Java language 1. Sort any 10 keys using Min Heap. 2. Sort any 10 keys using...
Java language 1. Sort any 10 keys using Min Heap. 2. Sort any 10 keys using Max Heap.
Sort the given keys using Counting sort algorithm. Also write the algorithm. 5, 2, 3, 1,...
Sort the given keys using Counting sort algorithm. Also write the algorithm. 5, 2, 3, 1, 0, 2, 1, 5, 0  
Language: Java Implement Merge Sort
Language: Java Implement Merge Sort
Write a program to sort the following using HeapSort. Use any language you want. A=[10, 8,...
Write a program to sort the following using HeapSort. Use any language you want. A=[10, 8, 7, 9,16, 14, 3, 2, 4, 1]
1. Sort the given keys using Counting sort algorithm. Also write the algorithm.          4, 1,...
1. Sort the given keys using Counting sort algorithm. Also write the algorithm.          4, 1, 0, 2, 1, 5, 0, 4                                                                     No code or programs, please. Manually solve the problem, please. Thanks
SHOW WORK Sort the given keys using Counting sort algorithm. Also write the algorithm.          5, 2,...
SHOW WORK Sort the given keys using Counting sort algorithm. Also write the algorithm.          5, 2, 3, 1, 0, 2, 1, 5, 0                                                                  SHOW WORK!
Write a program, using any language you want, to sort the following using QuickSort: {3, 4,...
Write a program, using any language you want, to sort the following using QuickSort: {3, 4, 5,1, 2, 6, 7, 8}
Implement heap sort by using the bottom-up insertion method. Add this sort to your sorting framework....
Implement heap sort by using the bottom-up insertion method. Add this sort to your sorting framework. Evaluate its performance in terms of the numbers of comparisons and exchanges, and compare it to the performance of the two advanced sorting methods that you have previously implemented. Submit your report with detailed empirical results and a thorough explanation of these results. Which of the three advanced sorting method is the best choice for a) ordered data, b) data in reverse order, and...
Implement Heap Sort and Quick Sort in different programs with the following specifications: 1. The input...
Implement Heap Sort and Quick Sort in different programs with the following specifications: 1. The input to the programs should be ASCII characters 2. Your program should be able to handle upper and lower case letters both 3. The sort should be done in a descending manner 4.Note: Please use array-based representation for these sorting algorithms Please write comment n explain each step clearly as well your program should show what you are taking as input array and what your...
USING JAVA Almost sort the array using Merge Sort. Perform Merge Sort as usual except that...
USING JAVA Almost sort the array using Merge Sort. Perform Merge Sort as usual except that during the final merge, it is not necessary to merge all n elements, but only the elements in positions 1 to k.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT