C++ Heap Implementation

Question

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

Answer 1

You constructHeap() function seems to use two different predicates for std::make_heap() and std::sort_heap(): I think it should rather be

std::make_heap(v.begin(), v.end(), pred);
std::sort_heap(v.begin(), v.end(), pred);

The precondition on the content of the range for std::sort_heap() is that the range is a heap according to the predicate.

BTW, in your abs_less function, you should just return the result:

template<class T>
bool abs_less<T>::operator()(const T& x, const T& y) const {
    return abs(x) > abs(y);
}

The result of the comparison is already a Boolean value. It doesn't become any more Boolean by return true or false.

Also unrelated to the actual question but instead of

while(!v.empty())
    v.pop_back();

You should probably use

v.clear();

or

v.erase(v.begin(), v.end());

Aside from being more readable, these versions are likely to be more efficient.