This is java In the recorded lectures, Sedgewick claims that the construction ph
ID: 3598592 • Letter: T
Question
This is java
In the recorded lectures, Sedgewick claims that the construction phase of heapsort takes linear time. Let's see it in action. Place your code in a files called MyHeapSort.java.
One way to implement sort with a heap is to add N items into a min-heap (that's the "construction" phase of sorting), then remove those items. They'll come out in sorted order. Implement this approach for N random integers, where N = 103, 106, and 109. What is the time spent in the construction phase and the removal phase for these input sizes? Do these agree with the expected rate of runtime growth?
A better way to construct the heap is provided in Algorithm 2.7 of the book (p.324), and can be copied from algs4.jar in the Heap.sort() function. Answer the same questions (time spent, and agreement with theory). In particular, what percentage of time does heapsort spend in the construction phase for N = 104, 106, and 108.
Explanation / Answer
Please find my implementation for Min Heap Sort.
public class MyHeapSort
{
public static 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);
}
}
static 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
static 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[] = {15,13,9,5,12,8,7,4,0,6,2,1};
System.out.println("Un-Sorted array is");
display(arr);
heapSort(arr);
System.out.println("Sorted array is");
display(arr);
}
}
/*
Sample run:
Un-Sorted array is
15 13 9 5 12 8 7 4 0 6 2 1
Sorted array is
0 1 2 4 5 6 7 8 9 12 13 15
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.