Question

(a) Implement the following algorithm, which is given a duplicate-free array array as input, in C++. whatDoIDo (array):

1) Build a heap from array (using buildHeap as explained in class), where the heap starts at position array[0].

2) Starting from j = size of array - 1, as long as j>0:

i. Swap the entries array[0] and array[j].

ii. Percolate down array[0], but only within the subarray array[0..j-1].

iii. Decrement j by 1. Provide three input/output examples for duplicate-free arrays of size about 10.

(b) What does whatDoIDo do? Explain your answer.

(c) What is the worst-case running time of whatDoIDo, in dependence of the size N of the given array? Explain your answer.

Answer 1

solution:

#include<iostream>
using namespace std;
void max_heapify(int *array, int i, int n)
{
int j, temp;
temp = array[i];
j = 2 * i;
while (j <= n)
{
if (j < n && array[j+1] > array[j])
j = j + 1;
if (temp > array[j])
break;
else if (temp <= array[j])
{
array[j / 2] = array[j];
j = 2 * j;
}
}
array[j/2] = temp;
return;
}
void build_maxheap(int *array,int n)
{
int i;
for(i = n/2; i >= 1; i--)
{
max_heapify(array,i,n-1);
}
}
void print_array(int *a,int n)
{
   int i=0;
   cout<<"-------------\n";
   while(i<n)
   {
       cout<<*(a+i)<<" ";  
       i++;
   }
   cout<<"\n------------------\n";
  
}
void whatDoIDo(int *array,int n)
{
   //step1 build heap..
   build_maxheap(array,n);
//   print_array(array,n);
   int j = n-1,k;
   while(j>0)
   {
       //swapping
       k=array[0];
       array[0]=array[j];
       array[j]=k;
          
       j--;//decrement..  
          
   }
  
   print_array(array,n);
  
}
int main()
{
   int n=10;
   int a[n],b[n],c[n];
   cout<<"Enter 10 elements for array 1:";
   int i=0;
   //reading 3 arrays...
   while(i<10)
   {
       cin>>a[i];  
       i++;
   }
  
   cout<<"Enter 10 elements for array 2:";
   i=0;
   while(i<10)
   {
       cin>>b[i];
       i++;  
   }
  
   cout<<"Enter 10 elements for array 3:";
   i=0;
   while(i<10)
   {
       cin>>c[i];  
       i++;
   }
  
  
   whatDoIDo(a,n);
   whatDoIDo(b,n);
   whatDoIDo(c,n);
  
   //c) worst case running time : O(n^2 logn)
  
  
  
   //21 22 23 24 25 26 27 28 29 30
   //11 12 13 14 15 16 17 18 19 20
   //1 2 3 4 5 6 7 8 9 10
   return 0;
}

output:-

Enter 10 elements for array 1:1 2 3 4 5 6 7 8 9 10
Enter 10 elements for array 2:11 12 13 14 15 16 17 18 19 20
Enter 10 elements for array 3:21 22 23 24 25 26 27 28 29 30
-------------
10 9 8 5 6 7 4 3 2 1
------------------
-------------
20 19 18 15 16 17 14 13 12 11
------------------
-------------
30 29 28 25 26 27 24 23 22 21
------------------

Process exited normally.
Press any key to continue . . .