Implement algorithm Heapify(A, i, j). Create an array A of size 10 with the foll
ID: 3860483 • Letter: I
Question
Implement algorithm Heapify(A, i, j). Create an array A of size 10 with the following values: 4, 2, 1, 8, 6, 5, 10, 9, 11, 16. Call Heapify(0, 9). Output the resulting array. Also indicate the time complexity by counting the number of times Heapify is called. (In Java Programming)
Algorithm Heapify(Note: The algorithm in the courseware uses A[1..n])
Input:Indices iand j. An array A[0..n-1] of key values.
Output:A[i] sinks to appropriate place in A[i..j]
Procedure Heapify(i, j)
if (2i+2 <=j) // A[i] has two children
Set k=index of max(A[2i+1],A[2i+2]) // kis index of the largest child
else if (2i+1 <=j) // A[i] has one child
Set k = 2i + 1 // // kis index of the largest (and only) child
else // A[i] has no children
return
if (A[i] < A[k])
Exchange(A[i],A[k])
Heapify(k, j)
Explanation / Answer
package Heap;
import java.util.Arrays;
public class Heap{
/**
* @param args the command line arguments
*/
public static Integer[] arr;
public static int count;
public Heap(){
count=0;
arr= new Integer[] { 4, 2, 1, 8, 6, 5, 10, 9, 11, 16 };
}
public static void main(String arg[]){
//Integer[] arr = new Integer[] { 4, 2, 1, 8, 6, 5, 10, 9, 11, 16 };
Arrays.sort(arr); // to sort the array
int cou=arr.length;
Heap obj=new Heap();
int c= obj.heapify(0,cou-1);
System.out.println("Heapify called no times. ="+c);
}
//Max method to find the index of max value
int max(int i){
if(arr[2*i+1] < arr[2*i+2]){
return 2*i+2;
}
else return 2*i+1;
}
//Swap method
private static void swap(int i, int k)
{
int tmp = arr[i];
arr[i] = arr[k];
arr[k] = tmp;
}
//heapify method
int heapify(int i, int j){
count=count+1;
int k=0;
if(2*i+2 <= j){
k=max(i);
}
else if (2*i+1 <=j){
k = 2*i + 1;
}
if(arr[i] < arr[k]){
swap(i,k);
heapify(k, j);
}
return count;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.