如何在Python中实现负无穷？

Question

我正在尝试实现一个基于堆的优先队列，这个算法来自《CLRS》书的第六章。下面是伪代码：

Max_Heap_Insert(A, key):
    A.heap_size = A.heap_size + 1
    A[A.heap_size] = -∞
    Heap_Increase_Key(A, A.heap_size, key)

我想问的是，在Python中，怎么定义负无穷大（-∞）呢？

Answer 1

我在自己做堆的实现时偶然发现了这个。 :)

从Python 3.5开始，你可以使用数学模块里的无穷大常量。

from math import inf
inf + inf                                        # inf
inf - inf                                        # nan
inf / inf                                        # nan
inf * inf                                        # inf
max(list(range(1_000_000)) + [inf])              # inf
min(list(range(-1_000_000, 1)) + [-inf])         # -inf

我之前不知道这个，所以用了一个自定义的类来实现相同的排序特性。

class MinusInf:      
    def __gt__(self, other):
        return False
    
    def __ge__(self):
        return False
    
    def __lt__(self, other):
        return True
    
    def __le__(self, other):
        return True
    
    def __eq__(self, other):
        return False


minus_inf = MinusInf()
minus_inf >= -1_000_000  # False

这样做可以满足堆的需求，但推荐的做法是直接使用 math.inf（或者 numpy.inf，这是来自numpy的无穷大常量）。

Answer 2

在Python 2中，None的值比任何整数都小，所以你可以直接用None。但是在Python 3中，你有至少四种选择：

1. 用最小值减去1，比如用min(A) - 1。
2. 使用None，每次比较两个值的时候，明确检查它们是否是None。
3. 定义一个新的数据类型，这个类型可以是一个整数或者负无穷（-∞），并且能正确处理比较。
4. 修改算法，让第二步不需要了。你需要想办法修补Heap-Increase-Key这个部分。

Answer 3

在Python中，有两个特别的值，分别是 float('inf') 和 float('-inf')。