自定义排序/最值/堆/平衡树的比较规则:自定义对象的小于方法

  |  

摘要: 自定义小于号

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


需求背景

在排序、取最值、堆、平衡树等场景中,我们都需要对两个元素之间比大小。如果要自定义比较逻辑,有两种方法。

第一种是比较函数,可以直接定义一个函数,好处是比较简单;也可以定义一个结构体并重载其调用运算符,好处是结构体中可以持有一些动态更新的状态。

第二种是重载元素的小于号,优点是比较直观。缺点是当元素为数值、字符等内置类型时不太好重载其小于号,并且也处理不了比较逻辑依赖动态更新的状态的情况。

一般来讲,建议优先使用重定义小于号的方式,当遇到数值、字符等内置类型,或比较逻辑依赖动态更新的状态时,再考虑定义比较函数解决。

本文我们把 C++ 和 Python 中自定义小于号的场景和相应的文章汇总一下。

C++

排序

文章 备注
扫描线算法(Line-Sweep) 区间按左右端点的顺序
射线旋转扫描线算法(Angular-Sweep) 区间按左右端点的顺序
【模板】二维向量的实现 向量按横纵坐标的顺序
直线和线段 直线方向向量的极角序
半平面交 直线方向向量的极角序
力扣LCP37-最小矩形面积 直线方向向量的极角序
leetcode第240场周赛 扫描线算法
力扣1707-与数组中元素的最大异或值 离线查询
二维偏序问题:扫描线+树状数组 点按横纵坐标的顺序
【组合数学】马拦过河卒 点按横纵坐标的顺序

文章 备注
leetcode第318场周赛 堆模拟
【搜索难题】力扣1263-推箱子 优先级队列BFS

平衡树

文章 备注
哈夫曼树与哈夫曼编码 实现哈夫曼树
平衡树优化DP 平衡树优化DP

Python

在Python中,__lt__方法是一个特殊方法(也称为魔术方法),用于定义小于的比较行为。当使用 < 运算符比较两个对象时,Python 解释器会调用该对象的 __lt__ 方法。

为了使比较操作直观且有用,通常建议也实现其他相关的比较方法,如__le__(小于等于),__eq__(等于),__ne__(不等于),__gt__(大于),和 __ge__(大于等于)。这样可以确保类的实例可以进行完整的比较操作。

文章 备注
优先级队列优化DP heapq 中维护自定义对象
Python标准库-数据结构 PriorityQueue 中维护自定义对象

Share