Question

Write a java class, MaxHeap, to implement a max-heap of values of type double. Use an array and be prepared to grow the array. The array implementation will probably be more efficient.

Next, write three java sorting methods:

a) One should be the heapsort algorithm.

b) the second should sort the array by inserting all the elements from the array into a heap defined by the MaxHeap class, and then removing all the items from the heap and putting them back into the array in order.

C) the third sorting method should be an optimized version of quicksort (randomized quicksort).

Answer 1

public class Main
{ 
  // first function here
  public void heapSort(int arr[]) 
  { 
    int n = arr.length; 

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

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

      sort(arr, i, 0); 
    } 
  } 
  
  // second function here
  void sort(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; 

        sort(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(); 
  } 

  public static void main(String args[]) 
  { 
      int arr[] = {20, 10, 30, 70, 50, 60}; 
      int n = arr.length; 

      Main ob = new Main(); 
      ob.heapSort(arr); 

      System.out.println("Sorted Array: "); 
      printArray(arr); 
  } 
}