forewaldinHo

class FibonacciHeap(BinomialHeap): #we inherit all methods from BinomialHeap.
    #Overwrite those you want to change, add new methods, do whatever you like :)
    def delete(self, node): #deletes a node from the heap
        if self._minTree == node:
            self._deleteMin()
        else:
            y = node.Parent
            x= node
            for child in node.Childlist:
                child._Parent = None
                child.Marked = False
            self._listOfTrees.extend(node.Childlist) # Tested( takes the children up)
            y._childlist.remove(node)

            while (y != None):

                if y.Parent == None:
                    break
                if (not y.Marked):
                    y.Marked = True
                    break
                else:
                    x = y
                    y = x.Parent
                    #self._listOfTrees.extend(node)
                    self._addTree(x)
                    x.Marked = False
                    y._childlist.remove(x)


    def decreaseKey(self, node, delta):
        y = node.Parent
        x = node
        y._childlist.remove(node)
        #self._listOfTrees.extend(node)
        self._addTree(node)
        node.Marked = False
        node._Parent = None
        node.Key= node.Key - delta
        self._updateMinPtrWithNewNode(node)
        while(y != None):
            #Rank implicit
            if y.Parent == None:
                break
            if not y.Marked:
                y.Marked = True
                break
            else:
                x = y
                y = x.Parent
                #self._listOfTrees.extend(node)
                self._addTree(x)
                x.Marked = False
                y._childlist.remove(x)



    def merge(self, other): #merges another Fibonacci Heap into this one
        self._listOfTrees.extend(other._listOfTrees)#Extend
        self._updateMinPtrWithNewNode(other._minTree)#Update minTree



    def insert(self, key, value): #inserts a new node with given key
        #and value into the heap
        node = HeapNode(key,value)
        self._addTree(node)
        return node

    def deleteMin(self): #removes and returns key and value of a node
        #with minimal key
        node = self._minTree
        for child in node.Childlist:
            child._Parent = None
            child.Marked = False
        self._listOfTrees.extend(node.Childlist)
        self._listOfTrees.remove(node)
        self._minTree = None # if its emptynow
        if(len(self._listOfTrees)>0): # Update MinTree Pointer
            self._minTree = self._listOfTrees[0]
            for potential in self._listOfTrees:
                 self._updateMinPtrWithNewNode(potential)
        self._tidyUp() #tidy up via bucketsort
        return node.Key, node.Value