Hey guys. I'm writing an heap-sort algorithm (code is below) but for someone reason my restore_heap function is incorrect somewhere. I understand how the algorithm is working. do y'all have any suggestions?

``````#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <ctime>
#include <algorithm>

using namespace std;

# if 0
void swap(int a[], int i, int j)
{
int temp;

temp = a[i];
a[i] = a[j];
a[j] = temp;
}
# endif

void make_heap(int a[], int n)
{
int k,i;
for(i=1;i<n;i++)
{
k=i;
int parent = (k-1)/2;

while(a[k] > a[parent])
{
swap(a[k],a[parent]);
k = parent;
parent = (k-1)/2;
}
}
}

void restore_heap(int a[], int n)
{
int k = 0;
int child = 2*k;
int lchild = child + 1;
int bchild = child + 2;

while((a[k]< a[lchild]||a[k] < a[bchild]) && (bchild) < (n-1))
{
if (a[bchild]> a[lchild])
{
swap(a[k],a[bchild]);
k = bchild;
bchild = (2*k)+2;
}

else
{
swap(a[k],a[lchild]);
k = lchild;
lchild =(2*k)+1;
}
}
}

bool is_heap(int a[],int n)
{
int k = 1;
int child = 2*k;

while (child <= (n-1)){
if(child < (n-1) && a[child] < a[child+1])
{
child++;
}
if(a[k] < a[child])
{
return false;
}
k++;
child = 2*k;
}
return true;
}

void heapsort(int a[], int n)
{
int k;
make_heap(a,n);

for(k = n-1; k>0; k--)
{
swap(a[0],a[k]);
restore_heap(a,k);
}
}

int g_ran(int a[], int n)
{
int i;
for (i=0; i<n; i++)
a[i]=rand()%100;

return a[n];
}

void print_out(int a[], int n)
{
int count=0;
for(int i=0; i < n; i++)
{
count++;
cout<<a[i]<<" ";
}
cout<<endl;
}

int main()
{
srand((unsigned)time(NULL));

int n;
cout<< "Size of array to be sorted: ";
cin>>n;

int * a = new int [n];
g_ran(a,n);
print_out(a,n);

make_heap(a,n);
print_out(a,n);

# if 0
if (is_heap(a,n) == make_heap(a,n))
{
cout<<"Loop Invariant is True!"<<endl;
}
else
{
cout<<"Loop Invariant is False! :-("<<endl;
}
return 0;
# endif

}
``````

## All 3 Replies

Can you post with code tags. Thanks.

CODE

``````#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <ctime>
#include <algorithm>

using namespace std;

# if 0
void swap(int a[], int i, int j)
{
int temp;

temp = a[i];
a[i] = a[j];
a[j] = temp;
}
# endif

void make_heap(int a[], int n)
{
int k,i;
for(i=1;i<n;i++)
{
k=i;
int parent = (k-1)/2;

while(a[k] > a[parent])
{
swap(a[k],a[parent]);
k = parent;
parent = (k-1)/2;
}
}
}

void restore_heap(int a[], int n)
{
int k = 0;
int child = 2*k;
int lchild = child + 1;
int bchild = child + 2;

while((a[k]< a[lchild]||a[k] < a[bchild]) && (bchild) < (n-1))
{
if (a[bchild]> a[lchild])
{
swap(a[k],a[bchild]);
k = bchild;
bchild = (2*k)+2;
}

else
{
swap(a[k],a[lchild]);
k = lchild;
lchild =(2*k)+1;
}
}
}

bool is_heap(int a[],int n)
{
int k = 1;
int child = 2*k;

while (child <= (n-1)){
if(child < (n-1) && a[child] < a[child+1])
{
child++;
}
if(a[k] < a[child])
{
return false;
}
k++;
child = 2*k;
}
return true;
}

void heapsort(int a[], int n)
{
int k;
make_heap(a,n);

for(k = n-1; k>0; k--)
{
swap(a[0],a[k]);
restore_heap(a,k);
}
}

int g_ran(int a[], int n)
{
int i;
for (i=0; i<n; i++)
a[i]=rand()%100;

return a[n];
}

void print_out(int a[], int n)
{
int count=0;
for(int i=0; i < n; i++)
{
count++;
cout<<a[i]<<" ";
}
cout<<endl;
}

int main()
{
srand((unsigned)time(NULL));

int n;
cout<< "Size of array to be sorted: ";
cin>>n;

int * a = new int [n];
g_ran(a,n);
print_out(a,n);

make_heap(a,n);
print_out(a,n);

# if 0
if (is_heap(a,n) == make_heap(a,n))
{
cout<<"Loop Invariant is True!"<<endl;
}
else
{
cout<<"Loop Invariant is False! :-("<<endl;
}
return 0;
# endif

}``````

Any suggestions???

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.