Implement a method to sort a given array using the heap sort algorithm. Use the
ID: 3785848 • Letter: I
Question
Implement a method to sort a given array using the heap sort algorithm. Use the algorithm from the textbook (see below). You should finish implementing Build Max Heap and Max Heapify by the end of lab. You can finish implementing the full algorithm for homework. Build-Max-Heap(A, n) for i = [n/2] downto 1 Max-Heapify (A, i, n) Heapsort(A, n) Build-Max-Heap(A, n) for i = n downto 2 exchange A [1] with A[i] Max-Heapify(A, 1, i - 1) Max-Heapify(A, i, n) l = Left(i) r = Right(i) if l lessthanorequalto n and A[l] > A[i] largest = l else largest = i if r lessthanorequalto n and A[r] > A[largest] largest = r if largest notequalto I exchange A[i] with A[largest] Max-Heapify(A, largest, n) Write a driver program to test the Heapsort algorithm for the arrays of varying lengths provided in Canvas. Use the input files provided earlier.Explanation / Answer
Hi, Please find my implementation.
Please let me know in case of any issue.
public class HeapSort
{
public void heapSort(int arr[])
{
int n = arr.length;
BuildMaxHeap(arr, n);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
MaxHeapify(arr, i, 0);
}
}
void BuildMaxHeap(int arr[], int n){
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
MaxHeapify(arr, n, i);
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void MaxHeapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
MaxHeapify(arr, n, largest);
}
}
/* A utility function to print array of size n */
public static void display(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[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
HeapSort ob = new HeapSort();
System.out.println("Un-Sorted array is");
display(arr);
ob.heapSort(arr);
System.out.println("Sorted array is");
display(arr);
}
}
/*
Sample run:
Un-Sorted array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.