[硕.Love Python] FibonacciHeap(F堆 & 斐波那契堆)

class Node(object):     __slots__ = [         'data', 'child', 'left', 'right',         'degree', 'parent', 'childCut',     ]     def __init__(self, data):         self.data = data         self.child = None         self.left = None         self.right = None         self.degree = 0         self.parent = None         self.childCut = False     def __str__(self):         return str(self.data)     __repr__ = __str__ class FibonacciHeap(object):     MAX_DEGREE = 20     def __init__(self):         self.root = None     def combine(self, heap):         self._dlistCombine(self.root, heap.root)         if heap.root.data < self.root.data:             self.root = heap.root     def insert(self, node):         if self.root is None:             self.root = node             self._initSiblingList(node)         else:             self._addSibling(self.root, node)             if node.data < self.root.data:                 self.root = node     def pop(self):         if self.root is None:             raise ValueError('pop from empty heap.')         res = self.root         self._clearParent(self.root.child)         children = self.root.child         siblings = self._dlistDelete(self.root)         self.root = self._rebuild(children, siblings)         return res     def delete(self, node):         if node is self.root:             self.pop()         else:             parent = node.parent             self._deleteChild(parent, node)             if node.child:                 self._clearParent(node.child)                 self._dlistCombine(self.root, node.child)             if parent:                 self._cascadingCut(parent)     def decrease(self, node, k):         print node.data, k         node.data -= k         print node.data         parent = node.parent         if parent and node.data < parent.data:             self._deleteChild(parent, node)             self._clearParent(node, False)             self._addSibling(self.root, node)             self._cascadingCut(parent)         if node.data < self.root.data:             self.root = node     def _cascadingCut(self, node):         while node.parent and node.childCut:             parent = node.parent             self._deleteChild(parent, node)             self._addSibling(self.root, node)             node = parent         if node.parent:             node.childCut = True     def _rebuild(self, children, siblings):         if children is None and siblings is None:             return None         treeArr = [None] * FibonacciHeap.MAX_DEGREE         self._combineTrees(treeArr, children)         self._combineTrees(treeArr, siblings)         head = None         treeIterator = iter(treeArr)         for node in treeIterator:             if node:                 break         root = head = prev = node         for node in treeIterator:             if node:                 prev.right = node                 node.left = prev                 prev = node                 if node.data < root.data:                     root = node         head.left = prev         prev.right = head         return root     def _combineTrees(self, treeArr, head):         if head is None:             return                   node = head         while True:             tmp = node             node = node.right             for i in xrange(tmp.degree, len(treeArr)):                 if treeArr[i] is None:                     break                 tmp = self._joinTree(tmp, treeArr[i])                 treeArr[i] = None             else:                 raise Exception('max degree')             treeArr[i] = tmp             if node is head:                 break     def _joinTree(self, tree1, tree2):         if tree2.data < tree1.data:             tree1, tree2 = tree2, tree1         self._addChild(tree1, tree2)         return tree1     def _dlistInit(self, head):         head.left = head.right = head     def _dlistCombine(self, head1, head2):         r1 = head1.right         l2 = head2.left         head1.right = head2         head2.left = head1         r1.left = l2         l2.right = r1     def _dlistInsert(self, head, node):         node.left = head         node.right = head.right          node.right.left = node         head.right = node     def _dlistDelete(self, node):         if node.left is node:             newHead = None         else:             node.left.right = node.right             node.right.left = node.left             newHead = node.right         return newHead     _initSiblingList = _dlistInit     _addSibling = _dlistInsert     def _addChild(self, parent, child):         if parent.child is None:             parent.child = child             self._initSiblingList(child)         else:             self._addSibling(parent.child, child)         child.parent = parent         child.childCut = False         parent.degree += 1     def _deleteChild(self, parent, child):         head = self._dlistDelete(child)         if parent:             parent.child = head             parent.degree -= 1             child.parent = None     def _clearParent(self, head, islist=True):         if head:             head.parent = None             if islist:                 node = head.right                 while node is not head:                     node.parent = None

                    node = node.right

刘硕老师Python精品课程：

《Python高级编程技巧实战》：

http://coding.imooc.com/class/62.html

 

《Python算法实战视频课程》：

http://edu.csdn.net/combo/detail/174

 

《Python科学计算—NumPy实战课程》：

http://edu.51cto.com/course/course_id-5046.html

 

熊猫TV直播间：

http://www.panda.tv/671023