
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; }