This is java. Please use Heap.sort() function from algs4.jar In the recorded lec

Question

This is java. Please use Heap.sort() function from algs4.jar

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.

Heap.sort() please use this code

Explanation / Answer

import java.util.Scanner; /* Class HeapSort */ public class HeapSort { private static int N; /* Sort Function */ public static void sort(int arr[]) { heapify(arr); for (int i = N; i > 0; i--) { swap(arr,0, i); N = N-1; maxheap(arr, 0); } } /* Function to build a heap */ public static void heapify(int arr[]) { N = arr.length-1; for (int i = N/2; i >= 0; i--) maxheap(arr, i); } /* Function to swap largest element in heap */ public static void maxheap(int arr[], int i) { int left = 2*i ; int right = 2*i + 1; int max = i; if (left arr[i]) max = left; if (right arr[max]) max = right; if (max != i) { swap(arr, i, max); maxheap(arr, max); } } /* Function to swap two numbers in an array */ public static void swap(int arr[], int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } /* Main method */ public static void main(String[] args) { Scanner scan = new Scanner( System.in ); System.out.println("Heap Sort Test "); int n, i; /* Accept number of elements */ System.out.println("Enter number of integer elements"); n = scan.nextInt(); /* Make array of n elements */ int arr[] = new int[ n ]; /* Accept elements */ System.out.println(" Enter "+ n +" integer elements"); for (i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.