[硕.Love Python] BinomialHeap(B堆 & 二项堆)

class Node(object):
    def __init__(self, data):
        self.data = data
        self.child = None
        self.left = None
        self.right = None
        self.degree = 0

    def __str__(self):
        return str(self.data)

    __repr__ = __str__

class BinomialHeap(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, data):
        node = Node(data)

        if self.root is None:
            self.root = node
            self._initSiblingList(node)
        else:
            self._addSibling(self.root, node)
            if data < self.root.data:
                self.root = node

    def pop(self):
        if self.root is None:
            raise ValueError('pop from empty heap.')

        res = self.root.data
        children = self.root.child
        siblings = self._dlistDelete(self.root)

        self.root = self._rebuild(children, siblings)

        return res

    def _rebuild(self, children, siblings):
        if children is None and siblings is None:
            return None

        treeArr = [None] * BinomialHeap.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)
        parent.degree += 1

if __name__ == '__main__':
    from random import sample

    data = range(1, 100000)
    data1 = sample(data, 1000)
    data2 = sample(data, 20000)

    heap1 = BinomialHeap()
    map(heap1.insert, data1)

    for _ in xrange(100):
        print heap1.pop(),
    print

    heap2 = BinomialHeap()
    map(heap2.insert, data2)

    heap1.combine(heap2)
    print '-' * 80
    for _ in xrange(200):
        print heap1.pop(),