CODEWITHSUNDEEP
pythonalgorithmnumbersinfinity
Bob Fang
Bob Fang

Reputation: 7411

How to implement negative infinity in Python?

I am trying to implement a Heap defined Priority Queue, the algorithm is from CLRS book chapter 6. The pseudocode is listed below:

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

My question is that using python, how do I define -∞?

Upvotes: 35

Views: 38539

Answers (4)

thanos.a
thanos.a

Reputation: 2694

Using the math library, you can do:

import math

a = -math.inf

Upvotes: 1

Chaos
Chaos

Reputation: 486

I stumbled across this while working on a heap implementation myself. :)

As of Python 3.5, you can use the inf constant from the math module

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

I did not know this and used a custom class to achieve the same ordering property

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

This will work for the purpose of a heap, but the recommended way is to just use math.inf (or numpy.inf which is the inf constant from numpy).

Upvotes: 4

Helpyhelperton
Helpyhelperton

Reputation:

Python has special values float('inf') and float('-inf').

Upvotes: 74

Yuval Filmus
Yuval Filmus

Reputation: 413

As it happens, in Python 2, None is less than any integer, so you can use None. In Python 3 you have (at least) four choices:

  1. Use min(A) - 1.
  2. Use None, and whenever you compare two values, explicitly test for them being None.
  3. Define a new data type that consists of either an integer or -∞, and handles comparisons correctly.
  4. Modify the algorithm so that line 2 is eliminated. You will have to patch Heap-Increase-Key somehow.

Upvotes: 6

Related Questions