A company (like Amazon) uses search in databases extensively and the databases n
ID: 3568606 • Letter: A
Question
A company (like Amazon) uses search in databases extensively and the databases need to be sorted frequently. Their favorite sorting algorithm is heapsort and they want to explore (and hopefully optimize) its performance. Given an array a[0..n-1], the task is to compute an array change[0..n-1] where change[i] is the number of times a[i] is changed when heapsort is performed on a[].
Write a program: stat(a[]) that computes array change[] and print it together with the total number of changes (the sum of the numbers in array change[]).
Explanation / Answer
public void Heapify(int heap[])
{
int left, r, min=0; // declare variables
left = 2 * i + 1; // left child
r = 2 * i + 2; // right child
if(heap[left] != null){ //Null condition to not give nullPointerException
if(left < size && heap[left] > heap[i]) // find smallest child
min = left; // save index of smaller child
else
min = i;
}
if(heap[r] != null){ //Null condition to not give nullPointerException
if(r < size && heap[r] > heap[min])
min = r; // save index of smaller child
}
if(min != i && i>=0 ) //It was not checking for i==0,so added that. // swap and percolate, if necessary
{
change[min]++; // this will record the number of time that data record is swapped.
tmp = heap[i]; // exchange values at two indices
heap[i] = heap[min];
heap[min] = tmp;
Heapify((i-1)/2); // call Heapify
}// end if
}// end method Heapify
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.