存放自定义数据类型的大/小根堆定义

要将小于(<)运算符重载函数改为适用于小根堆(即最小堆),您需要确保当传入对象的值小于当前对象的值时,函数返回true。这样,当您构建堆时,具有较小值的节点会被放置在较高的层次(即更接近堆顶)。

运算符重载工作方式:
当您已经有一个node类型的对象,并且您试图将它与即将传入的另一个node类型的对象(在这个例子中是cur)进行比较时(主要体现在先传入的已经在对象里,后传入的需要和其比较),C++编译器会查找适用于这两个对象类型的小于(<)运算符的实现。如果您已经在node类中重载了这个运算符,那么编译器就会使用您的重载函数。

bool operator <(const node &cur) const  
{  
    return dis < cur.dis;  
}

*this(隐式参数)代表当前对象,即调用运算符重载函数的对象。
cur是传递给函数的参数,代表您想要与当前对象进行比较的另一个node对象。
因此,当您比较两个node对象时,比如:

node a{...}; // 假设a已经初始化  
node b{...}; // 假设b已经初始化  
if (a < b) {  
    // ...  
}

在if (a < b)语句中,a是当前对象(*this)(因为先一步传入),而b是传递给<运算符重载函数的参数cur。重载函数会比较a.dis和b.dis的值,并根据a.dis是否小于b.dis来返回true或false。
在这个例子中,*this(即当前对象)与cur进行比较。
对于小根堆来说,重要的是确保堆顶元素(即堆中dis值最小的元素)始终位于顶部。通过重载小于运算符来确保具有较小dis值的节点在比较时被认为是“较小”的,这是维护小根堆性质的关键。

以下是一个适用于存放结构体的小根堆的比较逻辑

bool operator <(const node &cur) const   
{  
    return dis < cur.dis;  //如果当前对象的dis值小于传入参数的dis值,函数将返回true
}
//当前对象(即调用这个函数的node对象)就是与新节点(cur)进行比较的现有节点。

这确保了具有较小dis值的节点在堆中会被放置在更高的位置。因此,堆顶元素将始终具有当前堆中的最小dis值,这正是小根堆的特性。

再来一个适用于存放结构体的小根堆的比较逻辑

bool operator <(const node &cur) const     
{    
    return dis > cur.dis;//如果当前对象的dis值大于传入参数的dis值,函数将返回true
}

其他方法(以小根堆为例):
如果您正在使用std::priority_queue来实现堆,并且希望它作为小根堆,您可以在创建priority_queue时提供一个比较对象或lambda表达式来指定小根堆的行为:

假设 node 类已经定义 :
lambda 表达式定义小根堆

std::priority_queue<node, std::vector<node>, std::function<bool(const node&, const node&)>> minHeap([](const node &a, const node &b) {  
    return a.dis < b.dis;  
});  

函数对象:

struct cmp{  
    bool operator()(const node &a, const node &b) const {  
        return a.dis < b.dis;  
    }  
};  
priority_queue<node, std::vector<node>,cmp> minHeap;

在上面的代码中,无论是使用lambda表达式还是函数对象CompareDis,我们都指定了当a.dis小于b.dis时,a应该被认为“小于”b,这符合小根堆的性质。

相关推荐

  1. 存放定义数据类型大/小定义

    2024-04-03 04:12:01       44 阅读
  2. C语言中定义数据类型

    2024-04-03 04:12:01       51 阅读
  3. 【C语言】定义数据类型

    2024-04-03 04:12:01       26 阅读
  4. 定义类型详解(2)

    2024-04-03 04:12:01       48 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-03 04:12:01       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-03 04:12:01       100 阅读
  3. 在Django里面运行非项目文件

    2024-04-03 04:12:01       82 阅读
  4. Python语言-面向对象

    2024-04-03 04:12:01       91 阅读

热门阅读

  1. C++经典面试题目(十四)

    2024-04-03 04:12:01       38 阅读
  2. 免试生常问的一些问题汇总---专升本学习篇

    2024-04-03 04:12:01       39 阅读
  3. python内置函数 Z

    2024-04-03 04:12:01       38 阅读
  4. Nginx-记

    Nginx-记

    2024-04-03 04:12:01      34 阅读
  5. 第7单元日考

    2024-04-03 04:12:01       36 阅读
  6. LeetCode104.二叉树的最大深度

    2024-04-03 04:12:01       40 阅读
  7. mysql 存储过程示例

    2024-04-03 04:12:01       42 阅读
  8. 以下哪个变量不是指针类型

    2024-04-03 04:12:01       29 阅读
  9. LeetCode-41. 缺失的第一个正数【数组 哈希表】

    2024-04-03 04:12:01       42 阅读
  10. nginx输出日志配置与查看

    2024-04-03 04:12:01       38 阅读