Login
Order Now
Support
C++ Task on Algorithms & Data Structures

C++ Task on Algorithms & Data Structures

  • 5th May, 2022
  • 17:15 PM

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <fstream>
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<n; ++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: "<<t1<<" comparisons"<<endl;

    // 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: "<<t2<<" comparisons"<<endl;

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

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

Share this post

assignment helpassignment helperassignment expertsassignment writing services