@@ -30,17 +30,26 @@ def __init__(self, *argv):
3030
3131def insert (self ,key ):
3232self .__size += 1
33- if self .__root is None :
34- self .__root = self .Node (key )
33+ return self .__insert_root (self .Node (key ))
34+
35+ def __insert_root (self ,node ,change_root = True ):
36+ node .parent = None
37+ if not self .__root :
38+ self .__root = node
39+ self .__root .left = node
40+ self .__root .right = node
3541else :
36- new_node = self .Node (key ,left = self .__root .left ,right = self .__root )
37- self .__root .left .right = new_node
38- self .__root .left = new_node
39- if new_node .key < self .__root .key :
40- self .__root = new_node
42+ node .left = self .__root .left
43+ node .right = self .__root
44+ self .__root .left .right = node
45+ self .__root .left = node
46+
47+ if self .__root .key > node .key and change_root :
48+ self .__root = node
49+ return node
4150
4251def extract_min (self ):
43- if self .__root is None :
52+ if not self .__root :
4453return None
4554
4655result = self .__root
@@ -50,24 +59,28 @@ def extract_min(self):
5059child = self .__root .child
5160for i in xrange (0 ,self .__root .degree ):
5261next_node = child .right
53- self .__root .left .right = child
54- child .left = self .__root .left
55- self .__root .left = child
56- child .right = self .__root
57- child .parent = None
62+ self .__remove_self (child )
63+ self .__insert_root (child )
5864child = next_node
5965
6066# 移除根节点
61- self .__root .left .right = self .__root .right
62- self .__root .right .left = self .__root .left
67+ self .__remove_self (self .__root )
6368if self .__root .right is self .__root :
6469self .__root = None
6570else :
6671self .__root = self .__root .right
6772self .__extract_consolidating ()
6873
74+ result .left = result
75+ result .right = result
76+ result .parent = None
6977return result .key
7078
79+ @classmethod
80+ def __remove_self (cls ,node ):
81+ node .left .right = node .right
82+ node .right .left = node .left
83+
7184def __extract_consolidating (self ):
7285# 合并根链表
7386node_degrees = {}
@@ -100,19 +113,7 @@ def __extract_consolidating(self):
100113self .__root = None
101114
102115for d ,node in node_degrees .iteritems ():
103- node .parent = None
104- if self .__root is None :
105- self .__root = node
106- self .__root .left = node
107- self .__root .right = node
108- else :
109- node .left = self .__root .left
110- node .right = self .__root
111- self .__root .left .right = node
112- self .__root .left = node
113-
114- if self .__root .key > node .key :
115- self .__root = node
116+ self .__insert_root (node )
116117
117118@staticmethod
118119def __link_to (src ,dest ):
@@ -127,7 +128,7 @@ def __link_to(src, dest):
127128
128129dest_child = dest .child
129130src .parent = dest
130- if dest_child is None :
131+ if not dest_child :
131132dest .child = src
132133src .left = src
133134src .right = src
@@ -139,13 +140,39 @@ def __link_to(src, dest):
139140dest .degree += 1
140141
141142def union (self ,other ):
142- pass
143+ if not self .__root :
144+ self .__root = other .__root
145+ else :
146+ self_left = self .__root .left
147+ other_right = other .__root .right
148+ self .__root .left = other .__root
149+ other .__root .right = self .__root
150+ self_left .right = other_right
151+ other_right .left = self_left
152+ self .__root = self .__root if self .__root .key < other .__root .key else other .__root
153+ self .__size += other .__size
154+
155+ return self
143156
144157def min (self ):
145- return None if self .__root is None else self .__root .key
158+ return None if self .__root else self .__root .key
146159
147160def change_key (self ,node ,new_key ):
148- pass
161+ """
162+ 给node设置一个比其key小的值
163+ :param node:
164+ :param new_key:
165+ :return:
166+ """
167+ if node .key < new_key :
168+ return
169+ node .key = new_key
170+ parent = node .parent
171+ if parent and parent .key > node .key :
172+ self .__cut (node )
173+ self .__cascade_cut (parent )
174+ if self .__root .key > node .key :
175+ self .__root = node
149176
150177def __len__ (self ):
151178return self .__size
@@ -154,15 +181,62 @@ def delete(self, node):
154181self .change_key (node ,float ('-Inf' ))
155182self .extract_min ()
156183
184+ def __cut (self ,node ):
185+ parent = node .parent
186+ if not parent :
187+ return node
188+
189+ # 处理parent的child指针
190+ if node .right is node :
191+ parent .child = None
192+ else :
193+ parent .child = node .right
194+ self .__remove_self (node )
195+ parent .degree -= 1
196+ self .__insert_root (node )
197+ node .mark = False
198+ return node
199+
200+ def __cascade_cut (self ,node ):
201+ parent = node .parent
202+ # 如果parent为None，说明这个节点在根链表上，因此不需要继续处理
203+ if parent :
204+ if not node .mark :
205+ node .mark = True
206+ else :
207+ # 如果已经丢失了两个节点，那么要把本节点移到根链表上
208+ self .__cut (node )
209+ self .__cascade_cut (parent )
210+
157211
158212def main ():
213+ import random
159214test = ['O' ,'J' ,'S' ,'Y' ,'C' ,'M' ,'B' ,'R' ,'N' ,'F' ,'L' ,'Z' ,'U' ,'Q' ,'A' ,'G' ,'V' ,'E' ,'D' ,'W' ,'I' ,
160215'H' ,'T' ,'K' ,'X' ,'P' ]
161-
216+ random .shuffle (test )
217+ rele = 'Z'
218+ test .remove (rele )
162219heap = FibonacciHeap (* test )
220+ rnode = heap .insert (rele )
221+
222+ for i in xrange (0 ,random .randint (1 ,len (heap ))):
223+ print (heap .extract_min ())
224+
225+ print ("change a node key" )
226+ heap .change_key (rnode ,0 )
227+
163228for i in xrange (0 ,len (heap )):
164229print (heap .extract_min ())
165230
231+ print ("test union" )
232+ one = [10 ,20 ,0 ]
233+ other = [15 ,5 ,30 ]
234+ one_heap = FibonacciHeap (* one )
235+ other_heap = FibonacciHeap (* other )
236+ one_heap .union (other_heap )
237+ for i in xrange (0 ,len (one_heap )):
238+ print (one_heap .extract_min ())
239+
166240
167241if __name__ == "__main__" :
168242main ()
