Building a Minimum heap

Question

I am trying to build a min heap using the library function make_heap .Please point out the error in the class compare. The root element should have been the minimum element in the array but it is not.

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
class compare {
        bool operator()(pair<int, int> lhs,pair<int, int> rhs) const 
        {
            return lhs.second < rhs.second;
        }
    };
int main()
{
    int arr[]={9,2,5,7,3,5,7,5,4,5,6,4,5};
    make_heap(arr,arr+13,compare);
    cout<<arr[0];
}

What does "its not working" mean? What does it do, and what do you expect it to do? — Pete Becker, Sep 21 '13 at 17:00
*"It's not working"* is not a problem description. Other than concluding that it's probably just too lazy to work you're not going to get anything more substantial. — IInspectable, Sep 21 '13 at 17:00
I want to build a min heap using lib fn max_heap ...Plz suggest some way. I need it urgently. Plz i m a noob. — Anshul, Sep 21 '13 at 17:06

score 2 · Answer 1 · answered Sep 21 '13 at 17:04

2

Try

bool cmp(int l, int r) const
    {
        return l< r;
    }

i.e. not in a class (if you wish make it static

Then

make_heap(arr,arr+13,cmp);

answered Sep 21 '13 at 17:04

Ed Heal

59,252
17
87
127

score 1 · Answer 2 · answered Sep 21 '13 at 17:03

1

Why are you using a pair in your comparator ?

Use :

class compare {
public: //Make it public 
        bool operator()(const int &lhs, const int& rhs)  const
        {
            return lhs < rhs;
        }

    };

And then

int arr[]={9,2,5,7,3,5,7,5,4,5,6,4,5};
make_heap(arr,arr+13,compare()); //Notice ()
for(auto i:arr)
  cout<<i<<" ";

See HERE

answered Sep 21 '13 at 17:03

P0W

46,614
9
72
119

Do not need to pass ints as references - that is overkill. – Ed Heal Sep 21 '13 at 17:06
@EdHeal overkill in what sense ? I'm just sticking to `bool cmp(const Type1 &a, const Type2 &b);` from [here](http://en.cppreference.com/w/cpp/algorithm/make_heap) – P0W Sep 21 '13 at 17:10
Can u plz explain how do we use a comparator, I dint get what u did here, – Anshul Sep 21 '13 at 17:14
@P0W - In the sense that under the bonnet (hood for the yanks) references are implemented as pointers. Therefore just using the plain integer is cheaper. – Ed Heal Sep 21 '13 at 17:17
@Ed Can you point me to the section in the C++ standards that mandates how a compiler must implement references? – IInspectable Sep 21 '13 at 17:19
@Anshul A class with a overloaded `()` operator ,taking two `int`s for comparison. This is used with `std::make_heap`. Ref. [functor](http://stackoverflow.com/q/356950/1870232) for details – P0W Sep 21 '13 at 17:21
- How else would you implement them? – Ed Heal Sep 21 '13 at 17:22
@POW thnx u vei mch dude – Anshul Sep 21 '13 at 17:35
3

@Ed Not that I'm an authority on the topic, but my optimizer would probably consider passing an object by value when implementing a const reference. A `const int&` may likely wind up by value in a register, unless the C++ standard explicitly mandates how to implement references. Seeing that Microsoft's compiler generates identical code for `const int&` and `int` parameters I don't see the *"overkill"* you were talking about. – IInspectable Sep 21 '13 at 18:01
@llnspectable - Why rely on the compiler making assumptions when you can thwart it and be explicit – Ed Heal Sep 21 '13 at 18:03
1

@Ed I'm not relying on a compiler to make assumptions. I'm just open to the idea that optimizers are pretty damn smart these days. If you can follow a consistent scheme (as P0W did and explained) then by all means, do! If your team has coding conventions that mandate a different scheme then that's fine as well. Promoting dogmatic rules based on made up facts, on the other hand, is questionable. – IInspectable Sep 21 '13 at 18:16
@llnspectable - Why are you depending on the compiler being smart enough? Does that mean that a programmer is not clever enough to realise that not using references in this instance is a better option? – Ed Heal Sep 21 '13 at 18:24
1

@Ed I rely on a compiler being smart mostly because I don't have any evidence otherwise. I also do trust developers to be clever, hell, even I am! In a project of any size, however, I do value those developers who are consistent instead of clever. And I guess I simply don't see why passing a value is a better option, other than a compiler being free to generate worse code when passing a const reference. With compilers usually competing in generating good code this doesn't seem to be an issue. All of this is besides the point: If you provide a rationale make sure it's not made up. – IInspectable Sep 21 '13 at 18:50
2

@EdHeal You have the idea of a reference being a pointer, but that's only necessary for a non-const reference, a const reference is better thought of as an `alias` for an object. – user1095108 Sep 21 '13 at 23:47

Building a Minimum heap

2 Answers2