Alright, so I'm trying to implement a heap structure using a vector, however I cannot get this to work properly. The first heap works fine, but for some reason the stl sort_heap function is not working properly. I can't seem to get my heap to print in descending order. Here is my header:
// data files
#define D1 "***************************"
#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 and class prototypes
// stores items from input file into vector
template < class T >
void get_list ( vector < T >&, const char* );
// construct heap from items in vector
template < class T, class P >
void construct_heap ( vector < T >&, P );
// class to compare absolute values
template <class T> class abs_less {
public:
bool operator ( ) ( const T&, const T& ) const;
};
// structure to print items in heap, where T is data type of items,
// W is allocated size in printout, and L is max num of items printed
// on single line
template < class T, const int W, const int L >
struct print_list {
int sz, cnt; // size of heap and counter for printing
print_list ( const int&, const int& = 0 ); // constructor
void operator ( ) ( const T& );
};
and here is my source file:
int main ( )
{
vector < int > v1; // heap of integers
// first heap
cout << "first heap - ascending order:\n\n";
get_list ( v1, D1 );
construct_heap ( v1, less < int > ( ) );
print_list < int, INT_SZ, INT_LN > print1 ( v1.size ( ) );
for_each ( v1.begin ( ), v1.end ( ), print1 );
cout << "first heap - descending order:\n\n";
get_list ( v1, D1 );
construct_heap ( v1, greater < int > ( ) );
for_each ( v1.begin ( ), v1.end ( ), print1 );
cout << "first heap - ascending order with absolute values:\n\n";
get_list ( v1, D1 );
construct_heap ( v1, abs_less < int > ( ) );
for_each ( v1.begin ( ), v1.end ( ), print1 );
// print termination message
cout << "\t\t\t*** end of program execution ***\n\n";
return 0;
}
template<class T>
void get_list(vector<T> &v, const char *path) {
while(!v.empty())
v.pop_back();
ifstream file(path); // open file for input
T value; // temp value holder
while(file >> value) // read value in
v.push_back(value); // add value to vector
file.close(); // close file
}
template<class T, class P>
void construct_heap(vector<T> &v, P pred) {
make_heap(v.begin(), v.end()); // create heap
sort_heap(v.begin(), v.end(), pred); // sort heap according to pred
}
template<class T>
bool abs_less<T>::operator()(const T& x, const T& y) const {
if(abs(x) > abs(y))
return true;
else
return false;
}
template<class T, const int W, const int L>
print_list<T,W,L>::print_list(const int &s, const int &c) : sz(s), cnt(c) {
}
template<class T, const int W, const int L>
void print_list<T,W,L>::operator()(const T &x) {
if(cnt % L == 0 && cnt != 0)
cout << '\n';
cout << setw(W) << x << " ";
cnt++;
if(cnt == sz)
cout << '\n' << endl;
}
Here is the data in D1:
28 -647 -382 69 895 -655 404 -546
-9 -749 -831 -220 -444 -263 966 71
531 293 534 560 646 -695 251 -369
-305 834 40 -197 213 571 863 739
733 349 517 164 -220 -288 -598 654
-167 -72 958 -746 -573 916 475 -181
560 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
And here is my output. Why is my heap not printing in descending order?
first heap - ascending order:
-942 -925 -912 -912 -880 -831 -804 -761 -749 -746 -695 -677 -655 -647 -598
-573 -546 -539 -532 -525 -513 -509 -495 -444 -403 -390 -382 -369 -361 -361
-313 -305 -288 -282 -263 -235 -220 -220 -202 -197 -197 -187 -181 -167 -145
-136 -115 -72 -45 -9 -7 28 40 45 69 71 139 144 164 179
213 251 293 302 348 349 352 393 404 465 475 514 516 517 531
534 547 557 560 560 571 618 646 654 677 733 739 746 774 830
834 863 875 895 912 913 916 934 958 966
first heap - descending order:
958 916 746 913 895 875 739 534 863 834 618 830 774 733 677
531 293 393 654 646 352 571 560 516 -361 514 560 557 547 517
139 69 349 475 164 -220 45 -9 465 -167 -72 404 302 -202 348
251 40 28 -115 -305 -942 -444 -197 -513 -880 -912 179 144 71 -7
-45 -136 -761 -145 -495 -181 -525 -187 -197 -546 -220 -282 -235 -912 -677
-288 -598 -804 -313 -361 -509 -369 -539 -403 -390 -749 -925 -746 -695 -573
-831 -382 -532 -647 -263 213 912 934 -655 966