C++ STL make_heap and pop_heap not working

Question

I need to use a Heap, so i've searched about the STL one, but it doesn't seem to work, i wrote some code to explain what i mean:

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

struct data
{
    int indice;
    int tamanho;
};


bool comparator2(const data* a, const data* b)
{
    return (a->tamanho < b->tamanho);
}

int main()
{

        std::vector<data*> mesas;

        data x1, x2, x3, x4, x5;

        x1.indice = 1;
        x1.tamanho = 3;

        x2.indice = 2;
        x2.tamanho = 5;

        x3.indice = 3;
        x3.tamanho = 2;

        x4.indice = 4;
        x4.tamanho = 6;

        x5.indice = 5;
        x5.tamanho = 4;

        mesas.push_back(&x1);

        mesas.push_back(&x2);

        mesas.push_back(&x3);

        mesas.push_back(&x4);

        mesas.push_back(&x5);


        make_heap(mesas.begin(), mesas.end(), comparator2);

        for(int i = 0 ; i < 5 ; i++)
        {
            data* mesa = mesas.front();
            pop_heap(mesas.begin(),mesas.end());
            mesas.pop_back();

            printf("%d, %d\n", mesa->indice, mesa->tamanho);
        }

    return 0;
};

and this is what i get:

4, 6
2, 5
1, 3
3, 2
5, 4

So it's not working as a heap, as the maximum element on the vector is not being returned right.

Or am i doing something wrong?

Answer 1

You need to pass comparator2 to std::pop_heap since that is how you created the heap. Otherwise, it will use the default less than operator for pointers, which simply compares the pointer values.

Answer 2

MSN's answer is correct. However, either of a couple style guidelines can prevent this error:

• Declare the comparator to work on references, not objects, as operator< would. Use a vector of objects, not pointers.

  bool comparator2(const data& a, const data& b)
  {
      return (a.tamanho < b.tamanho);
  }
  

  You might really need the vector of pointers, in which case this doesn't apply.

• Use std::priority_queue (from <queue>), which ties together pop_heap and pop_back for you, remembering your comparator. This requires a functor comparator:

  struct comparator2 { bool operator()(const data& a, const data& b)
  {
      return (a.tamanho < b.tamanho);
  } };
   
  std::priority_queue<data, vector<data>, comparator2> mesas;
   // or std::priority_queue<data, vector<data>, comparator2>
  mesas.push(x1);
  

• Most elegant way is to make this the default comparison for data:

  struct data
  {
      int indice;
      int tamanho;
       
      friend bool operator<(const data& a, const data& b)
      {
          return (a.tamanho < b.tamanho);
      }
  };
  std::priority_queue<data> mesas;
  mesas.push(x1);
  

priority_queue can also take a prefilled unsorted container, which it will copy.