Hey all.. i am working on a assignment for class currently, and am having a few difficulties.

Right now i have a file that i am reading in, for each value read, i call my insert() function. This insert function push_bakc(item) into a vector, and then i call a function, upHeap() that should then recreate the heap structure as required. Then the next item is read from file, and the same thing occurs.

My problem seems to be within my upHeap() because when i get to a value i need to switch... such as:

9
3 7
5

5 needs to be moved up, but when i attempt to swap etc, it doesnt work and i get a crash.

So here is my current code:

#include "340.h"

#ifndef H_PROG6
#define H_PROG6

// data files

#define D1 "prog6.d1"
#define D2 "prog6.d2"
#define D3 "prog6.d3"

#define INT_SZ 4    // width of integer
#define FLT_SZ 7    // width of floating-pt number
#define STR_SZ 12   // width of string

#define INT_LN 15   // no of integers on single line
#define FLT_LN 9    // no of floating-pt nums on single line
#define STR_LN 5    // no of strings on single line

// function prototypes

template<class T,class U> 
void insert(vector<T>& vect, const T& input, U sortType)
{
     vect.push_back(input);   
     int index = vect.size() - 1;  
     upheap(vect, index, sortType);
}

template<class T,class U> 
T remove(vector<T>&, U);

template<class T,class U> 
void upheap(vector<T>& vect, int index, U sortType)
{
     while (index != vect[0])// && vect[index] < vect[index / 2 - 1])
         {
         if (vect[index] > vect[index /2 - 1])
             swap(vect[index], vect[index / 2 - 1]);
         //bool value = sortType(vect[index], vect[index / 2 - 1]);
         //if (value == true)
         //    swap(vect[index], vect[index / 2 - 1]);
         } 
}

template<class T,class U> 
void downheap(vector<T>&, int, U);


template<class T,class U>
void print_list(vector<T>& vect, const int input, const int lineSize, U sortType)
{
     int size1 = vect.size() -1 ;
      for(int j = 0; j < size1; j++)
    cout << vect[ j ] << " "; 
}

template<class T,class U>
void get_list(vector<T>& vect, const char* path, U sortType)
{
	T input;
	ifstream inFile;

	inFile.open(path);

	if (!inFile)
		return;

	while (inFile >> input)
	{
		cout << input << endl;
		insert(vect, input, sortType);
	}
	inFile.close();
}

#endif

If someone could take a look through i would be very happy :)

My driver program that calls these functions loooks like this:

int main()
{
    vector<int>    v1(1);   // heap of integers
    vector<float>  v2(1);   // heap of floating-pt nums
    vector<string> v3(1);   // heap of strings

    // print header message
    cout << "\t\t\t*** CSCI 340: Program 6 - Output ***\n\n";

    // sort and print first list

    cout << "first list - ascending order:\n\n";
    get_list(v1, D1, less<int>());
    print_list(v1, INT_SZ, INT_LN, less<int>());
..
...
}

Hope you guys could help me out.

>when i attempt to swap etc, it doesnt work and i get a crash
Step through your code and see what the indices are just before you crash. By the look of things, you're trying to use a negative index, which suggests your math is off. Keep in mind that a lot of heap algorithms are 1-based, and C++ is 0-based. This can cause off-by-one errors if you don't account for that.

Thanks for the reply. I noticed i was doing vect.size() - 1. When i do change this to vect.size() i get output to occur, but it seems to be incorrect... any ideas?

Here is the new output.../code

#include "340.h"

#ifndef H_PROG6
#define H_PROG6

// data files

#define D1 "prog6.d1"
#define D2 "prog6.d2"
#define D3 "prog6.d3"

#define INT_SZ 4    // width of integer
#define FLT_SZ 7    // width of floating-pt number
#define STR_SZ 12   // width of string

#define INT_LN 15   // no of integers on single line
#define FLT_LN 9    // no of floating-pt nums on single line
#define STR_LN 5    // no of strings on single line

// function prototypes

template<class T,class U> 
void insert(vector<T>& vect, const T& input, U sortType)
{
     vect.push_back(input);   
    [B] int index = vect.size();  [/B]
     upheap(vect, index, sortType);
}

template<class T,class U> 
T remove(vector<T>&, U);

template<class T,class U> 
void upheap(vector<T>& vect, int index, U sortType)
{
[B]     while (index != vect[0] && vect[index] < vect[index / 2 - 1])
         {
         if (sortType(vect[index] , vect[index / 2 - 1]))
             swap(vect[index], vect[index / 2 - 1]);
         } [/B]
}

template<class T,class U> 
void downheap(vector<T>&, int, U);


template<class T,class U>
void print_list(vector<T>& vect, const int input, const int lineSize, U sortType)
{
     int size1 = vect.size();
      for(int j = 0; j < size1; j++)
    cout << vect[ j ] << " "; 
}

template<class T,class U>
void get_list(vector<T>& vect, const char* path, U sortType)
{
	T input;
	ifstream inFile;

	inFile.open(path);

	if (!inFile)
		return;

	while (inFile >> input)
	{
		cout << input << endl;
		insert(vect, input, sortType);
	}
	inFile.close();
}

#endif

The output i seem to get now is:

0 0 -647 -382 0 0 -655 0 -546 -9 -749 -831 -220 -444 -263 0 0 0 0 0 0 0 -695 0 -369 -305 0 0 -197 0 0 0 0 0 0 0 0 -220 -288 -598 0 -167 -72 0 -746 -573 0 0 -181 0 516 913 -942 -361 514 -513 179 -912 912 -361 -880 -115 830 144 -761 139 -495 -7 -525 -45 -187 746 -145 -282 -235 -912 -677 45 393 -804 -197 547 -509 -313 -539 -403 -390 774 -925 302 -202 352 465 875 -532 677 934 557 -136 348 618

Not correct because there is only 1 '0' in my data file. But at least i dont get errors/crashes now!

Am i on the right track?

...also notice how i changed my upHeap() function also. I am using a predicate funtion called sortType which calls with less<>() or greater<>() functions from the STL depending on what is passed to the function initial from the driver mentioned above, then pass from function to function etc

I no longer get 0's in my code - i changed my size to be size - 1 , and that fixed that problem. I do though ... get a rather large random number in my code ... but any help in sortnig out my upHeap() function so that i will proberly go through my vector and create a heap, i would much appreicate it.. i will update you with any info as i work more

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