CODEWITHSUNDEEP
c++
psj01
psj01

Reputation: 3245

construct_heap template class function

I have a template function that takes in a vector and creates a heap

template<class T, class P> void construct_heap (vector <T>& v1, P pred)
 {
      make_heap(v1.begin(),v1.end());
      sort_heap(v1.begin(),v1.end(),pred);
 }

This works fine for ascending order . when i pass in construct_heap(v1, less()); it prints out the right data

but for descending order .. it doesn't work well.. i can't figure out why..

could someone please explain what I'm doing wrong here?

Thanks!

also attaching a pic of the output ..

OUTPUT

Upvotes: 1

Views: 134

Answers (1)

WhozCraig
WhozCraig

Reputation: 66194

The predicate used for making the initial max_heap should be the same as the predicate used during sorting. A general solution that works with all random-access containers below, demonstrated with both a vector and a deque.

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <random>

template<class T, template<class,class...> class C, class P, class... Args>
void construct_heap(C<T,Args...>& v, const P& pred)
{
    std::make_heap(std::begin(v), std::end(v), pred); // <<== same predicate
    std::sort_heap(std::begin(v), std::end(v), pred);
}

template<class T, template<class, class...> class C, class... Args>
void print_seq(std::ostream& os, const C<T,Args...>& v)
{
    for (auto x : v)
        os << x << ' ';
    os << '\n';
}

int main()
{
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<> dist(1,99);

    std::vector<int> v1;
    v1.reserve(25);
    std::generate_n(std::back_inserter(v1), v1.capacity(),
                    [&](){ return dist(rng);});
    print_seq(std::cout, v1);

    std::deque<int> d1(v1.begin(), v1.end());
    print_seq(std::cout, d1);

    construct_heap(v1, std::greater<int>());
    print_seq(std::cout, v1);

    construct_heap(d1, std::greater<int>());
    print_seq(std::cout, d1);

    return 0;

}

Output (obviously varies)

16 6 52 81 7 95 72 76 40 68 9 77 66 73 44 7 64 44 3 58 89 24 51 43 26 
16 6 52 81 7 95 72 76 40 68 9 77 66 73 44 7 64 44 3 58 89 24 51 43 26 
95 89 81 77 76 73 72 68 66 64 58 52 51 44 44 43 40 26 24 16 9 7 7 6 3 
95 89 81 77 76 73 72 68 66 64 58 52 51 44 44 43 40 26 24 16 9 7 7 6 3

Upvotes: 1

Related Questions