Question

Problem 3 (4+2+2 marks). (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

Answer:

(a)#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)
{

build_maxheap(array,n);
int j = n-1,k;
while(j>0)
{

k=array[0];
array[0]=array[j];
array[j]=k;
  
j--;
  
}
  
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;
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:

Screenshot of the code: