[硕.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