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

birk

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 is None:
　　
                    break
　　
                tmp = self._joinTree(tmp, treeArr)
　　
                treeArr = None
　　
            else:
　　
                raise Exception('max degree')
　　
            treeArr = 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(),