c++ - C++中自己的堆实现

Question

我必须用 C++ 编写自己的堆实现，它存储类型的对象：

std::pair<City, int>

其中 City 是一个存储两个整数的结构，它们代表城市坐标和字符串 - 城市名称。我确实知道如何使用纯整数来做到这一点，但是使用一对值对我来说有点问题。我已经开始编写我的堆类，但是，正如我所说，我不知道如何处理这些对。我希望堆按该对的 int 值排序。

Answer 1

如果您知道如何为ints 做这件事，那么您就快到了。像在赋值时对待 s 一样对待pair对象int，但出于比较目的，.second请直接使用而不是值。

Answer 2

您可以尝试使用std::make_heapwhich 将您的对序列放入堆顺序中，请参阅此在线示例。要仅按 int 值排序，请使用 C++11 lambda 表达式，该表达式将比较每对的第二个元素

或者，假设您不能使用任何与 STL 堆相关的算法，但给出任何自制的实现

template<typename RandomIt>
void my_make_heap(RandomIt first, RandomIt last)
{
     /* some algorithm using `a < b` to do comparisons */
}

您可以将其重写为（或添加重载）

template<typename RandomIt, typename Compare>
void my_make_heap(RandomIt first, RandomIt last, Compare, cmp)
{
     /* SAME algorithm, but now using `cmp(a, b)` to do comparisons */
}

然后将其称为my_make_heap(first, last, int_cmp)lambda 表达式比较像这样的对的位置：

    typedef std::pair<City, int> Element;
    auto int_cmp = [](Element const& lhs, Element const& rhs) {
         return lhs.second < rhs.second;
    };

Answer 3

所以据我了解：

你的结构是这样的，

struct node
{
   int X_coord;
   int y_coord;
   string name;
}

你需要根据pair的“int”值形成堆，称之为“x”。

所以你的对是

pair<node n , int x> ;

这是一个非常易读的堆代码，在一个类中实现。

它可以很容易地修改为您对 pair<> value 的要求。只需使用“heap.second”作为您的键值。