Question

For this problem, you may not look at any other code or pseudo-code (even if it is on the internet), other than what is on our website or in our book. You may discuss general ideas with other people. Assume A[1. . . n] is a heap, except that the element at index i might be too large. For the following parts, you should create a method that inputs A, n, and i, and makes A into a heap.

Answer 1

Answer:

(a)

(i) pseudo code :-

current = i

// assuming parent of root is -1

while A[parent] < A[current] && parent != -1 do,

if A[parent] < A[current] // if current element is bigger than parent then shift it up

swap(A[current],A[parent])

current = parent

(ii) In heap we create a complete binary tree which has height of log(n). In shift up we will take maximum steps equal to the height of tree so number of comparison will be in term of O(log(n))

(b)

(i) There are two cases while comparing with grandparent. If grandparent is less than current node then surely parent node also will be less than current node so swap current node with parent and then swap parent node with grandparent.

If above condition is not true then we will check for parent node and if it is less than current node then swap these.

pseudo code :-

current = i

// assuming parent of root is -1

parent is parent node of current node

while A[parent] < A[current] && parent != -1 do,

if A[grandparent] < A[current] // if current element is bigger than parent then shift it up

swap(A[current],A[parent])

swap(A[grandparent],A[parent])

current = grandparent

else if A[parent] < A[current]

swap(A[parent],A[current])

current = parent

(ii) Here we are skipping the one level so max we can make our comparison half from last approach, that would be (height/2)

so order would be log(n)/2

(iii) C++ code :-

#include<bits/stdc++.h>

using namespace std;

// function to return index of parent node

int parent(int i)

{

if(i == 0)

return -1;

return (i-1)/2;

}

// function to return index of grandparent node

int grandparent(int i)

{

int p = parent(i);

if(p == -1)

return -1;

else

return parent(p);

}

void shift_up(int A[], int n, int ind)

{

int curr = ind-1; // because array is 0-indexed

while(parent(curr) != -1 && A[parent(curr)] < A[curr])

{

int g = grandparent(curr);

int p = parent(curr);

if(g != -1 && A[g] < A[curr])

{

swap(A[curr],A[p]);

swap(A[p],A[g]);

curr = g;

}

else if(A[p] < A[curr])

{

swap(A[p],A[curr]);

curr = p;

}

}

}

int main()

{

int n;

cout<<"enter the number of elements :-\n";

cin>>n;

int A[n];

cout<<"enter the elements of array :-\n";

for(int i=0;i<n;i++)

cin>>A[i];

int ind;

cout<<"enter the index value :- \n";

cin>>ind;

shift_up(A,n,ind);

cout<<"array after shift up :-\n";

for(int i=0;i<n;i++)

cout<<A[i]<<" ";

cout<<endl;

}

Explanation: