[硕.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 = * 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(),
heap2 = BinomialHeap()
map(heap2.insert, data2)
heap1.combine(heap2)
print '-' * 80
for _ in xrange(200):
print heap1.pop(),
页:
[1]