// min heap solution
// extract k smallest data from a min-heap of all n data points
class K_Smallest_MinHeap {

public:

  K_Smallest_MinHeap(std::size_t n, std::size_t k): N(n), K(k), count(0)
    {  }

  void add(int value){
    values.push_back(value);
  }
  
  std::vector<int> get(){
    std::make_heap(values.begin(), values.end(), std::greater<>{});
    std::vector<int> result;
    for (std::size_t i = 0; i < K;   i){
      std::pop_heap(values.begin(), values.end(), std::greater<>{});
      result.push_back(values.back());
      values.pop_back();
    }
    return result;
  }
  
private:
  std::size_t N;
  std::size_t K;
  std::size_t count;
  std::vector<int> values;
};

Hi everyone

I do not understand the "std::greater<>{}" in std::make_heap()

I thought the takes only two iterators begin&end?

"void make_heap( RandomIt first, RandomIt last );"

Thank you for helping!

CodePudding user response：

The function std::make_heap is overloaded for two sets of parameters

template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

So the third parameter specifies explicitly the comparison function used to build a heap.

CodePudding user response：

According to the cppreference:

template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );

template< class RandomIt >
constexpr void make_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last,
                Compare comp );

template< class RandomIt, class Compare >
constexpr void make_heap( RandomIt first, RandomIt last,
                          Compare comp );

Constructs a max heap in the range [first, last). The first version of the function uses operator< to compare the elements, the second uses the given comparison function comp.

I do not understand the "std::greater<>{}" in std::make_heap()

I thought the takes only two iterators begin&end?

If your make_heap function only take two iterators, it will create a max_heap.

If you want to create a min_heap, you should use operator> to compare the elements, this is exactly what std::greater<>{} does.