C++堆实现

Question

好的，所以我尝试用向量来实现堆结构，但是我不能让它正常工作。第一个堆可以正常工作，但由于某种原因，stl sort_heap函数不能正常工作。我似乎无法按降序打印我的堆。这是我的标题：

// 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& );
};

这是我的源文件：

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;
}

以下是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

这是我的输出。为什么我的堆不按降序打印？

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

您的constructHeap()函数似乎为std::make_heap()和std::sort_heap()使用了两个不同的谓词:我认为应该是

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

std::sort_heap()的范围内容的先决条件是根据谓词范围是堆。

顺便说一句，在您的abs_less函数中，应该只返回结果：

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

比较的结果已经是一个布尔值。通过返回true或false，它不会变成任何布尔值。

也与实际问题无关，但是

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

你也许应该用

v.clear();

或

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

除了具有更高的可读性外，这些版本可能更有效率。