Write a method heapsort (int [] A, int nl to perform Heapsort using a maxheap on
ID: 3582334 • Letter: W
Question
Write a method heapsort (int [] A, int nl to perform Heapsort using a maxheap on the elements of A.
You may assume that the elements to be sorted are stored in A [ 1 .. n] and that A [ o J contains a sentinel value larger than any value in A [1 .. n].
You may also assume the existence of the following methods, and use them if required: trickleUp (int [] A, int i, int n) : trickle up from index i, in heap of size n trickleDown (int [] A, int i, int n) : trickle down from index i, in heap of size n swap ( int [] A, int i, int j) : in A, swap the item at index i with the item at index j
You may not assume that A[1 .. n] is already a max-heap before calling heapsort. Upon exit from heap sort, the elements of A [1 .. n] should be in increasing order.
Explanation / Answer
Hi, Friend, 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.