Nov 24, 2014 at 2:49am UTC
working on a reheapify downwards problem but I'm receiving a seg fault idk where the problem might be
#include <cstdlib> // Provides EXIT_SUCCESS, unsigned int
#include <iostream>
#include <algorithm>
using namespace std;
void make_heap(int* data, unsigned int n);
unsigned int left_child(unsigned int k)
{
return (2*k+1);
}
unsigned int right_child(unsigned int k)
{
return (2*k+2);
}
unsigned int parent(unsigned int k)
{
return (k-1)/2;
}
void reheapify_down(int* data, unsigned int n)
{
unsigned int current;
unsigned int big_child_index;
bool heap_ok = false;
current = 0 ;
while((!heap_ok)
{
//cout<<data[left_child(current)]<<endl;
if(data[left_child(current)] > data[current])
{
big_child_index = left_child(current);
}
if(data[right_child(current)] > data[current])
{
big_child_index = right_child(current);
}
if(data[current] < data[big_child_index])
{
swap(data[big_child_index], data[current]);
current = big_child_index;
}
else
heap_ok = true;
}
}
void heapsort(int* data, unsigned int n)
// Library facilities used: stdlib.h
{
unsigned int unsorted = n;
make_heap(data, n);
while (unsorted > 1)
{
--unsorted;
swap(data[0], data[unsorted]);
reheapify_down(data, unsorted);
}
}
int main( )
{
const unsigned int N = 3000000;
const int MANY_TESTS = 10;
unsigned int i;
int test;
for (test = 0; test < MANY_TESTS; test++)
{
int* data = new int[N];
std::cout << test << std::endl;
for (i = 0; i < N; i++) data[i] = rand( );
heapsort(data, N);
bool sorted = true;
for (i = 0; i < N - 1; ++i)
{
if (data[i] > data[i + 1])
sorted = false;
}
if (!sorted)
std::cout << "not sorted" << std::endl;
delete [] data;
}
return 0;
}
Last edited on Nov 24, 2014 at 3:54am UTC