C++ 堆实现

Question

好的，所以我正在尝试使用 vector 实现堆结构，但是我无法让它正常工作。第一个堆工作正常，但由于某种原因，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);
}

比较的结果已经是一个 bool 值。它不再通过返回 true 或 false 变成 bool 值。

也与实际问题无关但不是

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

你可能应该使用

v.clear();

或

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

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