Question
Need help please use JAVA, the instructions and driver are included below. Needs to run exactly as the Example Print Out shows it. Thanks in advanced.
Create a couple of classes that will simulate a process heap. Download the driver and follow the following instructions!
//DRIVER:
Create a class called Process
Instance variables:
Priority: which is an integer value that corresponds to where it will be in the heap. Needs to be greater than 0.
Time: A double value that corresponds to how long the process will take to run. Needs to be greater than 0.
Name: A string value that is the name of the process
Constructors: Default and Parameterized
Accessors and mutators for each instance variable
Make sure to check for valid values.
Other methods:
toString: a method that prints out the name, priority, and time
Create another class called ProcessHeap
Instance variables:
Heap: an array of type Process which represents the heap
Size: the number of elements in the heap
Constructors: Default and parameterized
Other methods:
insert: this method which returns nothing adds a new element to the heap. It always adds the next element as the next element in breadth order and then bubbles it up based on the priority of the Process.
peek: this returns the head of the heap
remove: This returns the root of the heap and then removes it from the heap. It must then move the last element in the heap (via breadth order) to the root and bubble that value down until it
Explanation / Answer
import java.util.Arrays; public class HeapSort { public static int heapSize; public static int LEFT(int i) { //returns left index of a zero index based array return 2*i+1; } public static int RIGHT(int i) { //returns right index of a zero based array return 2*i+2; } public static void BUILD_MAX_HEAP(int A[]) { heapSize = A.length;//heap size initialised for(int i=A.length/2; i>=0;i--)//since n/2, n/2+1 ... are leaves we can start from n/2 step downwards { //call MAX_HEAPIFY on each root node starting from n/2 MAX_HEAPIFY(A, i); } } public static void MAX_HEAPIFY(int A[],int i) { int l=LEFT(i);//the left element's index which is 2*i+1 (for zero based indexed array) int r=RIGHT(i);//right index = 2*i+2; int largestElementIndex = -1;//index can't be negative so initialise largest index , it will be used later //heapSize is the current size of the heap being worked upon //check if left index lies within the heap. //if element at left index is greater than root(A[i]) element, max heap property is violated //copy the index of violated element in largestElementIndex if(lA[i]){ largestElementIndex = l; } else //if max heap property is not violated copy the root's index in largestElementIndex { largestElementIndex=i; } //check to see the right sub tree for max heap property violation //here the largestElementIndex is calculated from previous step if(rA[largestElementIndex]) { largestElementIndex = r; } //if root doesn't has the largest index then swap the largest element with root element if(largestElementIndex!=i) { int temp = A[i]; A[i]=A[largestElementIndex]; A[largestElementIndex]=temp; //after swap, recursively call the MAX_HEAPIFY on the largest index(root element) MAX_HEAPIFY(A, largestElementIndex); } } public static void HEAP_SORT(int A[]) { //max heap is built with heapSize initialised BUILD_MAX_HEAP(A); //starting from end loop through entire array for(int i=A.length-1;i>=0;i--) { //since heap is already heapified and maintains max heap property //the first element of the array is root of max heap //swap it with the extreme element of the array i.e. setting the largest element to the end of array int temp = A[0]; A[0]=A[i]; A[i]=temp; //reduce the heap window by 1 heapSize = heapSize-1; //call max heapify on the reduced heap MAX_HEAPIFY(A,0); } } public static void main(String[] args) { int A[] = new int[]{4,1,3,2,16,9,10,14,8,7}; HEAP_SORT(A); System.out.println(Arrays.toString(A)); } }