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
}