Question

Explain this code: The structure used is max heap using array. C++

(i is the index of the element to be deleted)

void del(int i)
{
   int left,right,temp;

   arr[i]=arr[n-1];
   n=n-1;
   left=2*i+1; /*left child of i*/
   right=2*i+2; /* right child of i*/
   while(right < n)
   {
       if( arr[i]>=arr[left] && arr[i]>=arr[right] )
           return;
       if( arr[right]<=arr[left] )
       {
           temp=arr[i];
           arr[i]=arr[left];
           arr[left]=temp;
           i=left;
       }
       else
       {
           temp=arr[i];
           arr[i]=arr[right];
           arr[right]=temp;
           i=right;
       }
       left=2*i+1;
       right=2*i+2;
   }/*End of while*/
   if( left==n-1 && arr[i]    {   temp=arr[i];
       arr[i]=arr[left];
       arr[left]=temp;
   }
}

*********************************************************************************88

FULL CODE : fur more background info

#include
using namespace std;

int arr[100], n;

void insert(int num,int loc){
   int par;
   while(loc>0)
   {
       par=(loc-1)/2;
       if(num<=arr[par])   {
           arr[loc]=num;
           return;
       }
       arr[loc]=arr[par];
       loc=par;
   }/*End of while*/
   arr[0]=num; /*assign num to the root node */
}/*End of insert()*/

void del(int i)
{
   int left,right,temp;

   arr[i]=arr[n-1];
   n=n-1;
   left=2*i+1; /*left child of i*/
   right=2*i+2; /* right child of i*/
   while(right < n)
   {
       if( arr[i]>=arr[left] && arr[i]>=arr[right] )
           return;
       if( arr[right]<=arr[left] )
       {
           temp=arr[i];
           arr[i]=arr[left];
           arr[left]=temp;
           i=left;
       }
       else
       {
           temp=arr[i];
           arr[i]=arr[right];
           arr[right]=temp;
           i=right;
       }
       left=2*i+1;
       right=2*i+2;
   }/*End of while*/
   if( left==n-1 && arr[i]    {   temp=arr[i];
       arr[i]=arr[left];
       arr[left]=temp;
   }
}

void display(){
int i;
   if(n==0){
       cout<< "Heap is empty\n" ;
       return;
   }
   for(i=0;i        cout<<" "<    cout<<"\n";
}/*End of display()*/

main(){
   int choice,num;
   n=0;/*Represents number of nodes in the heap*/
   while(1){
       cout<<"1. Insert\n";
       cout<<"2. Delete root\n";
       cout<<"3. Display\n";
       cout <<"4. Find maximum element\n";
       cout<<"5. Quit\n";
       cout<<"Enter your choice : " ;
       cin>> choice ;
       switch(choice){
       case 1:
           cout<<"Enter the number to be inserted : " ;
           cin>>num ;
           insert(num,n);
           n=n+1;
           break;
       case 2:
           del(0);
           break;
       case 3:
           display();
           break;
       case 4:
           cout << "Maximum element in the heap is "<< arr[0] << endl;
           break;
       case 5:
           exit(0);
       default:
           cout<<"Wrong choice\n" ;
       }/*End of switch */
   }/*End of while */
}/*End of main()*/

Answer 1

void del(int i)//element at index i will be deleted
{
int left,right,temp;//declaring variables

//while deleting an element from max heap,
//the element at current index i, is replaced by last element of the heap
arr[i]=arr[n-1];//replacing element at index i, with last element

n=n-1;//decreasing size of heap

//now we need to perform down heaping from index i
//down heap: swapping value at present index i with one of its larger childs index (either left=2*i+1 or right=2*i+2) if it is greater than the current element

left=2*i+1; /*left child of i*/
right=2*i+2; /* right child of i*/
while(right < n)//while right is less than then n//performing down heaping
{
if( arr[i]>=arr[left] && arr[i]>=arr[right] )//if current element at index i, is greater than both of its childs then
return;//simply returning //because heap property satisfied
//one of its child must be greater than current element at i
//now finding it
if( arr[right]<=arr[left] )//if left child is greater then
{//swapping left child value and current element at index i value
temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
i=left;
}
else
{//if right child is greater then
//swapping right child value and current element at index i value
temp=arr[i];
arr[i]=arr[right];
arr[right]=temp;
i=right;
}
left=2*i+1;
right=2*i+2;
}/*End of while*/
//if left child is greater then
if( left==n-1 && arr[i] <arr[left])//this line is modified
{ ////swapping left child value and current element at index i value
       temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
} //after completing down heaping
//exiting from method
}

//PLS give a thumbs up if you find this helpful, it helps me alot, thanks.

//if you have any doubts, ask me in the comments