关于eager binomial heaps的内容详见算法设计搬运（3）——Heaps，更多细节在后面的Lazy Binomial Heaps也有。比较懒用的双向链表写的。双向链表可以实现 的 decreaseKey 和 deleteMin，可以参考石溪的ppt，尽管它是用array来存heap指针。有的ppt就错得离谱，单向链表decreaseKey就不只是在树的一个路径上比较了，没法
找它的left。
资源已上传，新手上路，就只当为熟悉python指针练手...
# author: zyx
# eager binomial heaps
# merge,insert,find_min,extractMin
class Binomial_Heap():
def __init__(self):
self.head = None
self.min = None
def merge(self,H2):
if not self.min:
self.min = H2.min
elif not H2.min:
return
else:
if self.min.data > H2.min.data:
self.min = H2.min
h1 = self.head
h2 = H2.head
unique_order_heap = Binomial_Heap()
c = unique_order_heap.head
while h1 and h2:
if h1.order == h2.order:
if h1.data <= h2.data:
h1.order+=1
h2.pre = None
d = h2
h2 = h2.sibling
d.sibling = h1.Lchild
d.parent = h1
h1.Lchild = d
if unique_order_heap.head == None:
unique_order_heap.head = h1
c = h1
h1.pre = None
h1 = h1.sibling
else:
h1.pre = c
c.sibling = h1
h1 = h1.sibling
c = c.sibling
else:
h2.order += 1
h1.pre = None
d = h1
h1 = h1.sibling
d.sibling = h2.Lchild
d.parent = h2
h2.Lchild = d
if unique_order_heap.head == None:
unique_order_heap.head = h2
c = h2
h2.pre = None
h2 = h2.sibling
else:
h2.pre = c
c.sibling = h2
h2 = h2.sibling
c = c.sibling
elif h1.order < h2.order:
if unique_order_heap.head == None:
unique_order_heap.head = h1
c = unique_order_heap.head
h1.pre = None
h1 = h1.sibling
else:
if h1.order == c.order:
if c.data <= h1.data:
c.order += 1
d = h1
h1.pre = None
h1 = h1.sibling
d.sibling = c.Lchild
c.Lchild = d
d.parent = c
else:
if c.pre == None: # single B
unique_order_heap.head = h1
h1.pre = None
else:
c.pre.sibling = h1
h1.pre = c.pre
h1.order += 1
c.sibling = h1.Lchild
h1.Lchild = c
c.parent = h1
c = h1
h1 = h1.sibling
else:
c.sibling = h1
h1.pre = c
h1 = h1.sibling
c = c.sibling
else:
if unique_order_heap.head == None:
unique_order_heap.head = h2
c = unique_order_heap.head
h2.pre = None
h2 = h2.sibling
else:
if h2.order == c.order:
if c.data <= h2.data:
d = h2
c.order += 1
h2 = h2.sibling
d.sibling = c.Lchild
c.Lchild = d
d.parent = c
else:
if c.pre == None: # single B
unique_order_heap.head = h2
h2.pre = None
else:
c.pre.sibling = h2
h2.pre = c.pre
h2.order += 1
c.sibling = h2.Lchild
h2.Lchild = c
c.parent = h2
c = h2
h2 = h2.sibling
else:
c.sibling = h2
h2.pre = c
h2 = h2.sibling
c = c.sibling
if c:
c.sibling = None
while h1:
if c:
if h1.order == c.order:
if c.data <= h1.data:
c.order += 1
d = h1
h1.pre = None
h1 = h1.sibling
d.sibling = c.Lchild
c.Lchild = d
d.parent = c
else:
if c.pre == None: # single B
unique_order_heap.head = h1
h1.pre = None
else:
c.pre.sibling = h1
h1.pre = c.pre
h1.order += 1
c.sibling = h1.Lchild
h1.Lchild = c
c.parent = h1
c = h1
h1 = h1.sibling
else:
c.sibling = h1
h1.pre = c
break
else:
unique_order_heap.head = h1
h1.pre = None
break
while h2:
if c:
if h2.order == c.order:
if c.data <= h2.data:
d = h2
c.order += 1
h2 = h2.sibling
d.sibling = c.Lchild
c.Lchild = d
d.parent = c
else:
if c.pre == None: # single B
unique_order_heap.head = h2
h2.pre = None
else:
c.pre.sibling = h2
h2.pre = c.pre
h2.order += 1
c.sibling = h2.Lchild
h2.Lchild = c
c.parent = h2
c = h2
h2 = h2.sibling
else:
c.sibling = h2
h2.pre = c
break
else:
unique_order_heap.head = h2
h2.pre = None
break
self.head = unique_order_heap.head
def find_Min(self):
return self.min
def insert(self,item):
node = Binomial_Trees(item)
H2 = Binomial_Heap()
H2.head = node
H2.min = node
self.merge(H2)
def extractMin(self):
m = self.min
if m.pre:
m.pre.sibling = m.sibling
else:
self.head = m.sibling
if m.sibling:
m.sibling.pre = m.pre
new_heap = Binomial_Heap()
to_transform = m.Lchild
minimum = to_transform
while to_transform:
if minimum.data > to_transform.data:
minimum = to_transform
to_transform.parent = None
if not new_heap.head:
new_heap.head = to_transform
to_transform = to_transform.sibling
new_heap.head.sibling = None
else:
d = to_transform
to_transform = to_transform.sibling
d.sibling = new_heap.head
new_heap.head.pre = d
new_heap.head = d
new_heap.min = minimum
cur = self.head
minimum = self.head
while cur:
if minimum.data < cur.data:
minimum = cur
cur = cur.sibling
self.min = minimum
self.merge(new_heap)
return m.data
class Binomial_Trees():
def __init__(self,item):
self.order = 0
self.parent = None
self.sibling = None
self.Lchild = None
self.data = item
self.pre = None
if __name__ == '__main__':
a = Binomial_Heap()
a.insert(1)
a.insert(2)
a.insert(3)
a.insert(4)
a.insert(-1)
a.extractMin()
a.extractMin()
b = Binomial_Heap()
b.insert(2)
b.insert(5)
b.insert(0)
b.insert(3)
a.merge(b)
a.insert(-1)
