Question

In: Computer Science

implement heap sort algorithm continuing off this #include <iostream> #define MAX_INT 2147483647 using namespace std; int...

implement heap sort algorithm continuing off this

#include <iostream>
#define MAX_INT 2147483647
using namespace std;

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

int* array;
int arraySize = 1;


// Get the size of the sequence
cin >> arraySize;
array = new int[arraySize];

// Read the sequence
for(int i=0; i<arraySize; i++){

cin >> array[i];

}

Solutions

Expert Solution

#include <iostream>
#define MAX_INT 2147483647
using namespace std;
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
  
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
  
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
  
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
  
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
  
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
  
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
  
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int main(int argc,char **argv) {

int* array;
int arraySize = 1;


// Get the size of the sequence
cout <<"Enter arrayszie: ";
cin >> arraySize;
array = new int[arraySize];

// Read the sequence
cout<<"Enter elements: ";
for(int i=0; i<arraySize; i++)
   cin >> array[i];
cout<<"Array Before Sorting: ";
printArray(array,arraySize);
heapSort(array,arraySize);
cout<<"Array After Sorting: ";
printArray(array,arraySize);
}

/* OUTPUT */

/* PLEASE UPVOTE */


Related Solutions

Do an insertion sort based off this code #include <iostream> #define MAX_INT 2147483647 using namespace std;...
Do an insertion sort based off this code #include <iostream> #define MAX_INT 2147483647 using namespace std;    int main(int argc,char **argv) { int* Sequence; int arraySize = 1; // Get the size of the sequence cin >> arraySize; Sequence = new int[arraySize];    // Read the sequence for(int i=0; i<arraySize; i++) cin >> Sequence[i];
write the algorithm for this the code?!. #include<iostream> using namespace std; #include<string.h> int main() { char...
write the algorithm for this the code?!. #include<iostream> using namespace std; #include<string.h> int main() { char plain[50], cipher[50]="", decrypt[50]=""; int subkeys[50], len;       cout<<"Enter the plain text:"<<endl; cin>>plain;    cout<<"Enter the first subkey:"<<endl; cin>>subkeys[0];    _strupr(plain);    len = strlen(plain);    /**********Find the subkeys**************/    for(int i=1; i<len; i++) { if ((plain[i-1]>='A') && (plain[i-1]<='Z')) { subkeys[i] = plain[i-1]-65; } }    /****************ENCRYPTION***************/       for(int i=0; i<len; i++) { if ((plain[i]>='A') && (plain[i]<='Z')) {    cipher[i] = (((plain[i]-65)+subkeys[i])%26)+65; }...
#include <cstring> #include <stdio.h> #include <iostream> using namespace std; int main() {        const int...
#include <cstring> #include <stdio.h> #include <iostream> using namespace std; int main() {        const int SIZE = 20;     char str[SIZE];     char str1[SIZE];     int n;     int k =1;        printf("Enter a word: \n");     fgets(str,SIZE,stdin);     printf("Enter another word: \n");     fgets(str1,SIZE,stdin);        if (str1[strlen(str1) - 1] == '\n')     {         str1[strlen(str1)-1] = '\0';     }     if (str[strlen(str) - 1] == '\n')     {         str[strlen(str)-1] = '\0';     }      ...
How do i make this program accept strings? #include <iostream> #include <algorithm> using namespace std; int...
How do i make this program accept strings? #include <iostream> #include <algorithm> using namespace std; int binaryToOctal(char digits[], int a) { int number; if (digits[0] == '0') { if (digits[1] == '1') if (digits[2] == '0') return 2; //found "010" else return 3; //found "011" else if (digits[1] == '0') if (digits[2] == '1') return 1; // found "001" else return 0; //found "000" } else { if (digits[0] == '1') if (digits[1] == '1') if (digits[2] == '0') return...
#include <iostream> using namespace std; int main() {     int hour;     int min;     for (hour = 1;...
#include <iostream> using namespace std; int main() {     int hour;     int min;     for (hour = 1; hour <= 12; hour++)     {         for (min = 0; min <= 59; min++)         {             cout << hour << ":" << min << "AM" << endl;         }     }       return 0; } 1.      Type in the above program as time.cpp. Add a comment to include your name and date. Compile and run. 2.      What is the bug or logic error in the above program? Add the...
#include <iostream> #include "lib.hpp" using namespace std; int main() {    // declare the bool bool...
#include <iostream> #include "lib.hpp" using namespace std; int main() {    // declare the bool bool a = true; bool b= true;    //Print the Conjunction function cout<<"\n\nConjunction Truth Table -"<<endl; cout<< "\nP\tQ\t(P∧Q)" <<endl; cout<< a <<"\t"<< b <<"\t"<< conjunction(a,b) <<endl; cout<< a <<"\t"<< !b <<"\t"<< conjunction(a,!b) <<endl; cout<< !a <<"\t"<< b <<"\t"<< conjunction(!a,b) <<endl; cout<< !a <<"\t"<< !b <<"\t"<< conjunction(!a,!b)<<endl;    //Print the Disjunction function cout<<"\n\nDisjunction Truth Table -"<<endl; cout<< "\nP\tQ\t(PVQ)" <<endl; cout<< a <<"\t"<< b <<"\t"<< disjunction(a,b) <<endl;...
#include <iostream> #include "lib.hpp" using namespace std; int main() {    // declare the bool bool...
#include <iostream> #include "lib.hpp" using namespace std; int main() {    // declare the bool bool a = true; bool b= true;    //Print the Conjunction function cout<<"\n\nConjunction Truth Table -"<<endl; cout<< "\nP\tQ\t(P∧Q)" <<endl; cout<< a <<"\t"<< b <<"\t"<< conjunction(a,b) <<endl; cout<< a <<"\t"<< !b <<"\t"<< conjunction(a,!b) <<endl; cout<< !a <<"\t"<< b <<"\t"<< conjunction(!a,b) <<endl; cout<< !a <<"\t"<< !b <<"\t"<< conjunction(!a,!b)<<endl;    //Print the Disjunction function cout<<"\n\nDisjunction Truth Table -"<<endl; cout<< "\nP\tQ\t(PVQ)" <<endl; cout<< a <<"\t"<< b <<"\t"<< disjunction(a,b) <<endl;...
#include <iostream> #include <iomanip> using namespace std; int main() {     int studentid, numberreverse[20], count =...
#include <iostream> #include <iomanip> using namespace std; int main() {     int studentid, numberreverse[20], count = 0, maximum = 0, minimum = 0;     cout << "Enter your student ID number: ";     cin >> studentid;     cout << "Student ID Number = " << studentid << endl;     while (studentid != 0)     {          numberreverse[count] = studentid % 10;          if (count == 0)          {              minimum = numberreverse[count];              maximum = minimum;          }          else...
#include <iostream> #include <fstream> #include <string> using namespace std; const int QUIZSIZE = 10; const int...
#include <iostream> #include <fstream> #include <string> using namespace std; const int QUIZSIZE = 10; const int LABSIZE = 10; const int PROJSIZE = 3; const int EXAMSIZE = 3; float getAverage(float arr[], int size) { float total = 0; for (int i = 0; i < size; i++) { total += arr[i]; } return total/size; } // the following main function do.... int main() { ifstream dataIn; string headingLine; string firstName, lastName; float quiz[QUIZSIZE]; float lab[LABSIZE]; float project[PROJSIZE]; float midExam[EXAMSIZE];...
#include<iostream> using namespace std; int main() {    int number_resistors;    double Resistors;    double series;...
#include<iostream> using namespace std; int main() {    int number_resistors;    double Resistors;    double series;    double parellel;    cout << "how many resistors: ";    cin >> number_resistors;    while (number_resistors != 0)    {        cout << "Enter the values of" << number_resistors << " resistors ";        for (int i = 0; i < number_resistors; i++) {            cin >> Resistors;            series += Resistors;                parellel...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT