Question

1. (10 points) Write a program to implement Heapsort. The input should be an array of size at least 15. Have the user enter the values or you can specify your own array (unsorted). The output should be the final sorted array AND print out the values in the max heap (just the heap, NOT the full array) after each MAX-HEAPIFY (after BUILD- MAX-HEAP i.e. don't print output in BUILD-MAX-HEAP) in your Heapsort procedure. Be careful with array indices. In the pseudo-code the first of element of the array is index 1 (not 0). Below is the pseudo-code for each of the procedures you will use: Array: A[n], indexed from 1 to n. LEFT (i) = 2i, RIGHT (i) = 21+1 MAX-HEAPIFY (A, i) 1=LEFT (i) r=RIGHT (i) if i <= A.heap-size and A[1] > A[i] largest = 1 else largest = i if r <= A.heap-size and A[r] > A[largest] largest = r if largest != i swap A[i] with A[largest] MAX-HEAPIFY (A, largest) BUILD-MAX-HEAP (A) A.heap-size = A.length for i = floor (A.length/2) down to 1 MAX-HEAPIFY (A, i)

How do I write this in the c++ language?

Answer 1

I HAVE IMPLEMENTED THE ABOVE ALGORITHMS TO SORT THE ARRAY USING HEAP.

I HAVE PASTED THE CODE AND OUTPUT SCREENSHOT.

#include<stdio.h> #include<conio.h> #include<math.h> #include<stdlib.h> #include<iostream> using namespace std; int heap_size=8; int sort_count=0; int parent(int i) {    return (floor(i)); } int left(int i) {    return 2*i; } int right(int i) {    return (2*i+1); } void printarray(int *a,int n) {    int i=0;    //cout<<"\n\t....THE SORTED ARRAY IS\t ";    cout<<"INDEX"<<endl;    for(i=1;i<=n;i++)        cout<<i<<"\t";    cout<<endl<<"ELEMENTS:"<<endl;    for(i=1;i<=n;i++)        cout<<a[i]<<"\t";    cout<<endl;       cout<<"*******************************************************************"<<endl; } void MAX_HEAPIFY(int *a,int i) {    int l,r,largest,temp;    l=left(i);    r=right(i);    if(l<=heap_size && a[l]>a[i] )        largest=l;    else        largest=i;    if(r<=heap_size && a[r]>a[largest])        largest=r;    if(largest!=i)    {        temp=a[i];        a[i]=a[largest];        a[largest]=temp;        MAX_HEAPIFY(a,largest);    }    sort_count++;    printarray(a,i); } void BUILD_MAX_HEAP(int *a,int length) {    int i=0;    for(i=floor(length/2);i>=1;i--)        MAX_HEAPIFY(a,i); } void HEAPSORT(int *a,int length) {    int i=0,temp=0;    BUILD_MAX_HEAP(a,length);    for(i=length;i>=1;i--)    {        temp=a[i];        a[i]=a[1];        a[1]=temp;        heap_size--;        MAX_HEAPIFY(a,1);           } } void readarray(int *a,int l) {    int i;    cout<<"\n....Enter "<<l<<" values ";    for(i=1;i<=l;i++)        cin>>a[i]; } int main() {    int *a;    int length=8;    cout<<"******************************************"<<endl;    cout<<"* HEAP SORT PROGRAM * "<<endl;    cout<<"******************************************"<<endl;    cout<<"\n....Enter number of values \n\t";    cin>>length;    heap_size=length;    a=(int*)malloc(sizeof(int)*length);    readarray(a,length);    cout<<"******************************************"<<endl;    cout<<"* THE GIVEN ARRAY IS * "<<endl;    cout<<"******************************************"<<endl;    printarray(a,length);    cout<<"******************************************"<<endl;    cout<<"* THE INTERMENDIATE MAX HEAP *"<<endl;    cout<<"******************************************"<<endl;    HEAPSORT(a,length);    //printarray(a,length);    cout<<"******************************************"<<endl;    cout<<"* THE SORTED ARRAY IS *"<<endl;    cout<<"******************************************"<<endl;    printarray(a,length);    cout<<"******************************************"<<endl;    cout<<"* THE WORST CASE COMPLEXITY IS *"<<endl;    cout<<"******************************************"<<endl;    cout<<"\tNumber of elements:"<<length<<"\n O(nln(n)): "<<(sort_count-length); }

OUTPUT:

CAV Command Prompt D:\My DS LAB\heap>g++ HEAP_SORT_WITH_TIMECOMPLEXITY.cpp D:\My DS LAB\heapa HEAP SORT PROGRAM .... Enter number of values | 15 .... Enter 15 values 5 641198711132 * THE GIVEN ARRAY IS 三三三三三三三三三三三三、塞,需要,重要,重重重重重重重重重重重重重重重 INDEX ( 3 4 5 ( 6 6 7 8 9 16 11 12 13 14 15 ELEMENTS: 15 14 13987 12 16 11 13 2 家家家来来来来来来来来来来来来来来来来来来来深深深深深深深深深深深深深深深深深深深深深深米米米米米米米米米米米米米米家家家家家家家家 家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家原素家家家家家家家家 THE INTERMENDIATE MAX HEAP 家家家家原素家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家 INDEX 三三三三三三三三三三三三三三三三三三三三三三三三三三三三三三三三三三三三。 ELEMENTS: 564 15 14 139

1 2 INDEX ELEMENTS: INDEX 1 2 ELEMENTS: 21 INDEX ELEMENTS: INDEX ELEMENTS: INDEX ELEMENTS: 家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家 三三三三三三三三三三三三三三三三三三三三三三三三三三三 * THE SORTED ARRAY IS INDEX 1 2 ELEMENTS: ( 3 4 4 5 5 6 6 7 7 8 8 9 9 16 10 11 11 12 12 13 13 14 14 15 15 1 2 这家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家 家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家 * THE WORST CASE COMPLEXITY IS 家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家家 Number of elements:15 O(nln(n)):42

Complexity Analysis:

Since we are building a heap in tree fashion the number for comparisions for each element With respect to its parent is ln(n).

we nedd to compare n elements with its parent so ,

the time complexity is O(n ln (n))

for example consider n =15

ln(15)=2.70805

=>O(nln( n))=15*2.708.5=40.62 (which is an approimation of above result).