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:
