Java Language! Code the Reheap Downward algorithm in a static method and code a

Question

Java Language!

Code the Reheap Downward algorithm in a static method and code a driver program to demonstrate that it functions properly. The array to be built into a heap should be passed to the method. Then, modify the Reheap Downward method coded before so that the index of the root node of the tree and the size of the array are passed to the method as parameters: reheapDown(int [] array, int root,intsize). Provide a driver program to demonstrate that the method functions properly. In each case, output the contents of the array before and after the method is invoked. Also, code the Heap Sort algorithm and provide a driver program to demonstrate that it functions properly.

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 reheapDown(int A[],int root,int size) { heapSize = size-root;//heap size initialised for(int i=heapSize/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+root); } } 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}; reheapDown(A,0,A.length); System.out.println(Arrays.toString(A)); } }

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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