The Reason of Using 'Std::Greater' for Creating Min Heap via 'Priority_Queue'

The reason of using `std::greater` for creating min heap via `priority_queue`

The logical argument is as follows

1. std::priority_queue is a container adaptor; basic memory considerations make the back the preferred place for modifications (with pop_back() and push_back()) for sequence containers such as std::vector.
2. the priority_queue primitives are based on std::make_heap (constructor), std::pop_heap + container::pop_back (priority_queue::pop) and on container::push_back + std::push_heap (priority_queue::push)
3. pop_heap will take the front of the underlying storage, and put it at the back, restoring the heap invariant afterwards. The reverse goes for push_heap.
4. doing sort_heap on a max_heap (with the max at the front initially) will repeatedly pop the front to the back and sort the range according to less (which is the default comparison operator)
5. hence, the preferred implementation of a max_heap is to have the max element w.r.t. less at the front, accessed through priority_queue::top (underlying container::front).
6. one can still debate whether it is intuitive that priority_queue with a std::less comparator is representing a max_heap. It could have been defined as a min_heap by reversing the comparator's arguments (but see the comment by @T.C. that with C++98 binders this is rather verbose) everywhere in the calls to the various heap functions. The one (for me) counter-intuitive result would have been that top() would then not have given the element with top priority

Min heap with std::priority_queue is my bottleneck

http://demangler.com translated that function into: (indented by me)

RKD<Division_Euclidean_space<float> >::nn(
  unsigned int,
  std::vector<float, std::allocator<float> > const&,
  float const&,
  std::vector<std::pair<float, int>, std::allocator<std::pair<float, int> > >&,
  int&,
  int,
  unsigned int*,
  std::priority_queue<std::tuple<float, int, int>,
                      std::vector<std::tuple<float, int, int>,
                                  std::allocator<std::tuple<float, int, int> > >,
                      std::greater<std::tuple<float, int, int> > >&,
  float const&,
  unsigned int const&,
  std::vector<float, std::allocator<float> > const&,
  std::vector<float, std::allocator<float> > const&,
  int)

I don't know what nn does, but I suppose it does a lot more than priority queue operations.

std::priority_queue and make_heap API design

I find it confusing too, but from a somewhat different perspective. Suppose that you want to sort a sequence in ascending order. There are several ways of doing it:

1. Put your data in a std::vector or std::deque and run std::sort() using std::less.
2. Put your data in a std::list and run std::list::sort() using std::less.
3. Insert your data in a std::set that is configured with std::less and in the end it is automatically sorted.
4. Put your data in a std::vector or std::deque and run std::make_heap() followed by std::pop_heap()-s using std::less.
5. Push your data through a std::priority_queue using std::greater (!!!).

As we can see, std::priority_queue is a definite outlier from such a point of view.

Actually, the reason behind the confusing behavior of std::priority_queue in this regard is hidden in item (4) since that is what a std::priority_queue does underneath. (4) is also against my intuition (though to a lesser extent), since in the intermediate state (while not all std::pop_heap have been performed) the sorted part of the sequence is in its upper range, rather than the lower range.

But it also explains why a max heap was selected for the standard library - std::pop_heap puts the popped element in the location, from where it can be removed in constant time, regardless of the container type used.

Type error in C++ when instantiating a priority_queue of int pairs with a custom comparator (to implement a min heap)

As you can see in the std::priority_queue documentation:

• The 1st template argument is the data type (should be pair<int,int> in your case).
• The 2nd template argument should be the underlying container type used for the queue.
• The 3rd should be the compare type.

For example if you want a priority_queue of int pairs that use std::vector as a container, you need:

std::priority_queue<std::pair<int, int>,                  // data type
                    std::vector<std::pair<int,int>>,      // container type
                    std::greater<std::pair<int,int>>> pq; // compare type

Note: as you can see here the std::pair implementation for comparison operators which are used by std::greater is:

Compares lhs and rhs lexicographically by operator<, that is, compares
the first elements and only if they are equivalent, compares the
second elements.

If this is not what you need you can implement your own compare type for std::pair<int,int>.

A side note: it is better to avoid using namespace std. See here: Why is "using namespace std;" considered bad practice?.

How to make a min heap of tuples sorted by the 2nd element?

You can do this in two ways:

1. Change the order of the tuple so the column you want to sort is the first in the tuple.

2. Create a custom comparator outside of your function definition.

    Struct Comparator {
       bool operator()(tuple<int, int>& t1, tuple<int, int>& t2) {
            return std::get<1>(t1) > std::get<1>(t2);
        }
    }
   

Then, you can use this comparator instead of greater<tuple<int, int>> as such:

    priority_queue<tuple<int, int>, vector<tuple<int, int>>, Comparator> pq;

This comes in very handy when you're dealing with complex objects and you want to sort by a specific attribute.

Why does priority_queue in STL not follow strict weak ordering?

The problem is that the negation of your strict_weak_order (that uses >) is <= and that is not a strict weak order. A strict weak order R has to satisfy x R x == false for all x. However, R equal to <= yields (x <= x) == true.

You need to reverse the order of arguments (which corresponds to <) instead.

bool comparer_function(const int& val1 , const int& val2){
    return strict_weak_order_function(val2 , val1);
}

struct Compaper_functor{
    bool operator()(const int& val1 , const int& val2){
        return strict_weak_order_function(val2 , val1);
    }
};

Note however that a std::priority_queue has a std::less as default comparator, but that gives a max-heap (i.e. [5, 4, 3, 2, 1] output from the same input), so to get a min-heap (i.e. with output [1, 2, 3, 4, 5] from input [5, 4, 3, 2, 1]) you need to pass std::greater, see e.g. this:

#include <queue>
#include <iostream>

int main()
{
    auto const v  = std::vector<int> { 5, 4, 3, 2, 1 };

    // prints 5 through 1
    for (auto p = std::priority_queue<int> { v.begin(), v.end()  }; !p.empty(); p.pop())
        std::cout << p.top() << ',';
    std::cout << '\n';

    // prints 1 through 5
    for (auto p = std::priority_queue<int, std::vector<int>, std::greater<int>> { v.begin(), v.end()  }; !p.empty(); p.pop())
        std::cout << p.top() << ',';
    std::cout << '\n';
}

Live Example

---

Related Topics