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

摘要: 自定义小于号

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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 中维护自定义对象

---