C++ Homework Help on Algorithms & Data Structures

• 5th May, 2022
• 17:15 PM

#include
#include
#include
#include
#include
using namespace std;

void heapify(int arr[], int n, int i, int & t1) 
{ 
    int largest = i; 
    int l = 2*i + 1; 
    int r = 2*i + 2;

    // If left child is larger than root 
    if (l < n){
        t1++;
        if(arr[l] > arr[largest])
            largest = l; 
    }
        
    // If right child is larger than largest so far 
    if (r < n){
        t1++;
        if(arr[r] > arr[largest]) 
            largest = r; 
    }

    // If largest is not root 
    if (largest != i) 
    { 
        int temp= arr[largest];
        arr[largest]=arr[i];
        arr[i]=temp;

        // Recursively heapify the affected sub-tree 
        
        heapify(arr, n, largest,t1); 
    } 
} 
/* A utility function to print array of size n */
void printArray(int arr[], int n) 
{
    for (int i=0; i         cout << arr[i] << " "; 
    cout << "\n"; 
} 

// function to do heap sort 
void heapSort(int arr[], int n) 
{     int t1=0,t2=0;

    // Build heap (rearrange array) 
    for (int i = n / 2 - 1; i >= 0; i--) {
        
        heapify(arr, n, i,t1); 
        
    }
    
    printArray(arr,n);    
    cout<<"InsertHeap: "<

    // One by one extract an element from heap 
    for (int i=n-1; i>0; i--) 
    { 
        // Move current root to end 
        
        int temp= arr[0];
        arr[0]=arr[i];
        arr[i]=temp;

        // call max heapify on the reduced heap 
        
        heapify(arr, i, 0,t2); 
    } 
    cout<<"DeleteRoot: "< } 

int main(int argc, char** argv) {

    for(int i=1;i     
        vector v;
        ifstream in(argv[i]);
        int val;
        while (in >> val)
        {
            v.push_back(val);
        }
        int arr[v.size()];
        for(int j=0;j         
            arr[j]=v[j];
        cout<<"Heap before sorting: "<         heapSort(arr,v.size());
        cout<<"Vector after sorting:"<         printArray(arr,v.size());
        cout<<"\n";
    }
    
    return 0;
}