python - 如何在python中实现负无穷大？

Question

我正在尝试实现一个堆定义的优先级队列，该算法来自 CLRS 书第 6 章。伪代码如下所示：

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 有特殊的值float('inf')和float('-inf').

Answer 2

碰巧的是，在 Python 2 中，None它小于任何整数，因此您可以使用None. 在 Python 3 中，您有（至少）四种选择：

1. 使用 min(A) - 1。
2. 使用None，并且每当您比较两个值时，显式测试它们是否为None。
3. 定义一个由整数或 -∞ 组成的新数据类型，并正确处理比较。
4. 修改算法以消除第 2 行。你将不得不以Heap-Increase-Key某种方式修补。

Answer 3

我在自己进行堆实现时偶然发现了这一点。:)

从 Python 3.5 开始，您可以使用数学模块中的 inf 常量

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 的 inf 常量）。