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

}

Edited 3 Years Ago by Reverend Jim: Fixed formatting

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

}
This article has been dead for over six months. Start a new discussion instead.