Thread: making min heap

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    30

    making min heap

    hi!
    to make a minheap out of a vector "cont" the function is make_heap(cont.begin(),cont.end(),greater<int>)

    now this works if the contents of the vector "cont" are single integers what do we do if it is a pair of int ie: cont<pair<int,int> >

    what change do I make to function operator greater<int>.

    thanks a lot.

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    You would need to create an operator> for pair<int, int>. A better solution would probably be to write an comparison function or object that does the same thing and specifying it instead of greater<int> (or rather greater<pair<int, int> >).

    Make a struct with the following function:
    Code:
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) const
    Then just implement that to return the ordering you want for your pair. Give the struct a name appropriate to the comparing you are doing (e.g. IntPairGreaterThan). Then pass that to the make_heap function as the third parameter.

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    30

    thanx a lot!

    Thanx a lot man that was really useful.
    Could you give me some reference from where I could learn about function objects?

    Regards!
    Eklavya

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    There is very little to learn about function objects. They are basically a struct (or class) with an overloaded operator() and may optionally have member variables to store state.

    Const correctness is important and to work with all std algorithms they need certain typedefs,which your function object gains if you inherit them from std::unary_function or std::binary_function (the references tell you which algorithms requires which predicates).

    For example, a function object to compare two pair<int, int>'s might look like this:
    Code:
    struct less_pair:
        public std::binary_function<std::pair<int, int>, std::pair<int, int>, bool>
    //template arguments for binary_function are: left argument type, right argument type, return type
    {
        bool operator() (const std::pair<int, int>& lhv, const std::pair<int, int>& rhv) const
        {
            return lhv.first < rhv.first || lhv.first == rhv.first && lhv.second < rhv.second;
        }
    };
    
    //usage
        std::vector<std::pair<int, int> > vec;
        //...
        std::sort(vec.begin(), vec.end(), less_pair());
    It might also be useful to familiarize yourself with the function objects that <functional> provides (they may save you the trouble of writing your own function objects in simpler cases).

    Another quite cool thing that may save you from having to write a separate functor - especially if you're just going to use it once - and may sometimes be the most readable option as well is the lambda header in boost.
    In this particular case (since we need to access members of pair a lot), it is probably not that helpful though
    Code:
        std::sort(vec.begin(), vec.end(),
            bind(&std::pair<int, int>::first, _1) < bind(&std::pair<int, int>::first, _2)
            || bind(&std::pair<int, int>::first, _1) == bind(&std::pair<int, int>::first, _2)
            && bind(&std::pair<int, int>::second, _1) < bind(&std::pair<int, int>::second, _2)
        );
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> Could you give me some reference from where I could learn about function objects?
    The C++ Standard Library by Josuttis is my reference for that stuff (and occasionally other books like The C++ Programming Language by Stroustrup and Effective STL by Meyers).

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    std::pair already has a less-than operator. If you want to define a greater-than comparison function, then I'd suggest simply calling the operator less-than operator of the pair with the arguments reversed. It'll probably be more efficient, and will certainly be less likely to have a bug.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Are you sure that's standard? I see dinkumware (meaning VC++) has it. In fact it has operator> already, so the original code would work with one minor change:
    Code:
    make_heap(cont.begin(),cont.end(),greater<pair<int, int> >);
    I just don't know if that's in the standard or just a VC++ extension.

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Wow! Good to know.

    This discussion still applies if you want to compare pairs in any other ways (only first or only second, etc).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #9
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by anon View Post
    an overloaded operator() and may optionally have member variables to store state.
    You should be careful with this though, because if the function object is intended to be used as a predicate to be passed to an STL function, it must be a stateless object.
    See Chapter 87. Make predicates pure functions for an explaination of why.

  10. #10
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Right.

    They may quite safely store unchanged data though, such as for example std::binder1st and std::binder2nd.

    Stuffing too much data in them might not be wise for performance reasons as it may be copied a lot?

    And then, not all function objects are predicates...
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  11. #11
    Registered User
    Join Date
    Jan 2008
    Posts
    30
    Quote Originally Posted by anon View Post
    There is very little to learn about function objects. They are basically a struct (or class) with an overloaded operator() and may optionally have member variables to store state.

    Const correctness is important and to work with all std algorithms they need certain typedefs,which your function object gains if you inherit them from std::unary_function or std::binary_function (the references tell you which algorithms requires which predicates).

    For example, a function object to compare two pair<int, int>'s might look like this:
    Code:
    struct less_pair:
        public std::binary_function<std::pair<int, int>, std::pair<int, int>, bool>
    //template arguments for binary_function are: left argument type, right argument type, return type
    {
        bool operator() (const std::pair<int, int>& lhv, const std::pair<int, int>& rhv) const
        {
            return lhv.first < rhv.first || lhv.first == rhv.first && lhv.second < rhv.second;
        }
    };
    
    //usage
        std::vector<std::pair<int, int> > vec;
        //...
        std::sort(vec.begin(), vec.end(), less_pair());
    It might also be useful to familiarize yourself with the function objects that <functional> provides (they may save you the trouble of writing your own function objects in simpler cases).

    Another quite cool thing that may save you from having to write a separate functor - especially if you're just going to use it once - and may sometimes be the most readable option as well is the lambda header in boost.
    In this particular case (since we need to access members of pair a lot), it is probably not that helpful though
    Code:
        std::sort(vec.begin(), vec.end(),
            bind(&std::pair<int, int>::first, _1) < bind(&std::pair<int, int>::first, _2)
            || bind(&std::pair<int, int>::first, _1) == bind(&std::pair<int, int>::first, _2)
            && bind(&std::pair<int, int>::second, _1) < bind(&std::pair<int, int>::second, _2)
        );
    thanks a lot man really descriptive.

  12. #12
    Registered User
    Join Date
    Jan 2008
    Posts
    30
    Quote Originally Posted by Daved View Post
    Are you sure that's standard? I see dinkumware (meaning VC++) has it. In fact it has operator> already, so the original code would work with one minor change:
    Code:
    make_heap(cont.begin(),cont.end(),greater<pair<int, int> >);
    I just don't know if that's in the standard or just a VC++ extension.
    i had tried this method but it seems to be giving huge "STL style" errors.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Do you know...
    By davejigsaw in forum C++ Programming
    Replies: 1
    Last Post: 05-10-2005, 10:33 AM
  2. Making control...
    By Finchie_88 in forum C++ Programming
    Replies: 2
    Last Post: 09-07-2004, 01:42 PM
  3. Variable Min and Max Program
    By EdanD in forum C Programming
    Replies: 8
    Last Post: 06-30-2004, 07:48 PM
  4. heap question
    By mackol in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 05:03 AM
  5. Is this really true or it's just science fiction?
    By Nutshell in forum A Brief History of Cprogramming.com
    Replies: 145
    Last Post: 04-09-2002, 06:17 PM