用于C ++中最小堆的比较器 [英] Comparator for min-heap in C++

问题描述

我试图使用STL make_heap 在C ++中创建 long 的最小堆 ¹ code>等，但我的比较器似乎没有正确比较。以下是我目前的比较器：

  struct greater1 {
 bool operator（）（const long& a，const long& ; b）const {
 return a> b; 
} 
};但是，当我执行 std :: pop_heap（humble.begin（））时，会出现这样的错误：
  



< ，humble.end（），g）; 其中 g 是 greater1 和 humble 是 sort_heap时创建 [9,15,15,25] 被调用，我得到一个 15 弹出。

什么可能会出错？

编辑：

我意识到我运行sort_heap没有比较器，而当我运行它比较器，我从 sort_heap 获取 [15,15,9,25] 。现在我想我的比较器绝对不工作，但不确定为什么。

¹ 默认情况下，STL会创建一个max-heap，所以我需要一个比较器。

解决方案

也许你在某个地方缺少某些东西，下面的代码如下所示：

  #include< vector> 
 #include< algorithm> 
 #include< iostream> 
 
 struct greater1 {
 bool operator（）（const long& a，const long& b）const {
 return a& 
} 
}; 
 
 int main（）{
 std :: vector< long>谦卑; 
 humble.push_back（15）; 
 humble.push_back（15）; 
 humble.push_back（9）; 
 humble.push_back（25）; 
 
 std :: make_heap（humble.begin（），humble.end（），greater1（））; 
 while（humble.size（））{
 std :: pop_heap（humble.begin（），humble.end（），greater1（））; 
 long min = humble.back（）; 
 humble.pop_back（）; 
 std :: cout<< min < std :: endl; 
} 
 
 return 0; 
} 
  

I am trying to make a min-heap¹ of longs in C++ using the STL make_heap, etc., but my comparator doesn't seem to be comparing properly. The following is my current comparator:

struct greater1{
    bool operator()(const long& a,const long& b) const{
        return a>b;
    }
};

However, when I do std::pop_heap(humble.begin(),humble.end(),g); where g is an instance of greater1 and humble is a heap who makes [9,15,15,25] when sort_heap is called, I get a 15 popped.

Is my comparator correct? what might be going wrong?

EDIT:
I realized that I am running sort_heap with no comparator, whereas when I run it this comparator, I get [15,15,9,25] from sort_heap. Now I am thinking my comparator is definitely not working, but unsure why.

¹The STL makes a max-heap by default, so I need a comparator.

解决方案

Perhaps you are missing something somewhere, the code below works as intended:

#include <vector>
#include <algorithm>
#include <iostream>

struct greater1{
  bool operator()(const long& a,const long& b) const{
    return a>b;
  }
};

int main() {
  std::vector<long> humble;
  humble.push_back(15);
  humble.push_back(15);
  humble.push_back(9);
  humble.push_back(25);

  std::make_heap(humble.begin(), humble.end(), greater1());
  while (humble.size()) {
    std::pop_heap(humble.begin(),humble.end(),greater1());
    long min = humble.back();
    humble.pop_back();  
    std::cout << min << std::endl;
  }

  return 0;
}

这篇关于用于C ++中最小堆的比较器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！