search

danielborowski / fibonacci-heap-python

Implementation of a Fibonacci heap in Python
MIT License
90 stars 37 forks source link

IndexError in consolidate function #7

Open MartinKern opened 4 years ago

MartinKern commented 4 years ago

In some cases there will be an IndexError in the consolidate function in line 122: A = [None] * int(math.log(self.total_nodes) * 2) int(math.log(self.total_nodes) * 2) is supposed to be the maximum number of distinct node degrees. This is however off by one and a bit. The node degree d is bound by where is the golden ratio (See Wikipedia). Doing the math I got . So the 2 needs to be replaced with something like 2.08. The number of possible distinct node degrees is one higher than this since nodes with a degree of zero need to be considered. The solution is to replace: A = [None] * int(math.log(self.total_nodes) * 2) with A = [None] * int(math.log(self.total_nodes) * 2.08 + 1)

ghost commented 3 years ago

There are two errors in the code and are both in the consolidate function. The first is the '<=' instead of '<' pointed out by the answer to another comment. The second is that the self.root_list doesn't get updated after the call to consolidate. Either way both errors can be fixed by substituting the last lines of consolidate with the following:

    for i in range(0, len(A)):
        if A[i] is not None:
            if A[i].key <= self.min_node.key:
                self.min_node = A[i]

    self.root_list = self.min_node