$25
CS5800-Homework 9 Solved
1 Exercise 17.3-3
Let the potential function to be Φ(Di) = kni ∗ ln(ni) where ni is the number of elements in the binary heap, and k is a big enough constant. The amortized of the ith operation with respect to potential function Φ is defined by Ci = Ci + Φ(Di) − Φ(Di−1)
a. INSERT
If the ith operation inserts into a nonempty heap, then ni = ni−1 + 1 and the amortized cost is
For , we have
If n ≥ 2, then
≤ 2kln(ni) + 2k
= O(lgni)
b. EXTRACT-MIN
If the ith operation extracts from a heap with more than 1 item, then ni = ni−1−1 and the amortized cost is
2 Exercise 17.3-6
Algorithm 1 Implement a queue using two stacks
1: function Enqueue-Stack(stack1,stack2,value)
2: stack1.push(value)
3: end function
4:
5: function Dequeue-Stack(stack1,stack2)
6: if stack2 is not empty then
7: return stack2.pop()
8: else
9: while stack1 is not empty do
10: stack2.push(stack1.pop())
11: end while
12: if stack2 is empty then
13: return −1
14: else
15: return stack2.pop()
16: end if
17: end if
18: end function
Use accounting method:
The actual costs of the operations were:
PUSH 1
POP 1
MULTIPOP min(k,s) where k is the argument supplied to MULTIPOP and s is the stack size when it is called.
Let’s assign the following amortized cost:
PUSH 2
POP 0
MULTIPOP 0
Amortized cost of ENQUEUE = 1+2 = 3
Amortized cost of DEQUEUE: if stack 2 is empty
Amortized cost = 20 = 1 if stack 2 is nonempty
Amortized cost = 1+0 = 1
Therefore, the amortized cost of both ENQUEUE and DEQUEUE are O(1).
3 Exercise 19.2-1
Figure 1: initial heap
Figure 2: step 1
Figure 3: step 2
Figure 4: step 3
Figure 5: step 4
Figure 6: step 5
Figure 7: after consolidate
4 Implement binomial heaps
class Node:
def i n i t ( self , k=None) :
s e l f .p = None s e l f . key = k s e l f . degree = 0 s e l f . child = None s e l f . sibling = None
class binomialHeap :
def i n i t ( self , head=None) :
s e l f . head = head
def make heap( s e l f ) : heap = binomialHeap () return heap
def minimum( s e l f ) : y = None x = s e l f . head mini = float ( ’ inf ’ ) while x != None:
if x . key < mini :
mini = x . key
y = x
x = x . sibling
return y
def link ( self ,y , z) :
y .p = z
y . sibling = z . child
z . child = y
z . degree += 1
def heap merge( self , h1 , h2) :
node = None
p = None p1 = h1 . head p2 = h2 . head
if p1 is None: return h2 . head if p2 is None:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 return h1 . head
44
45 if p1 . degree < p2 . degree :
46 p = p1
47 p1 = p1 . sibling 48 else :
49 p = p2
50p2 = p2 . sibling
51node = p
52
53while p1 and p2 :
54if p1 . degree < p2 . degree :
55p. sibling = p1 56p1 = p1 . sibling 57else :
58p. sibling = p2
59p2 = p2 . sibling
60p = p. sibling
61
62if p2 : 63p. sibling = p2 64else :
65p. sibling = p1
66return node
67
68def union ( self , h1 , h2) : 69 h = s e l f . make heap ()
70 h. head = s e l f . heap merge(h1 , h2)
71#free the object h1 and h2 but not the l i s t s they point to
72del h1
73del h2
74
75if h. head is None:
76return h
77
78prevx = None
79x = h. head
80nextx = x . sibling
81
82 while next x is not None:
83 if (x . degree != nextx . degree ) or ( next x . sibling is
not None and next x . sibling . degree == x . degree ) :
84 prev x = x #case 1 and 2 85 x = next x #case 1 and 2
86 elif x . key <= next x . key :
87
x . sibling = next x . sibling
#case
3
88
h. link ( next x , x)
#case
3
89
else :
90
if prev x is None:
91
h. head = next x
#case
4
92
else :
93
prev x . sibling = next x
#case
4
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
h. link (x , next x )
next x = x . sibling
return h
def heap insert ( self , x) :
h = s e l f . make heap () x .p = None
x . child = None
x . sibling = None
x . degree = 0
h. head = x heap = s e l f . union ( self , h) return heap
def insert ( self , key) : return s e l f . heap insert (Node(key) )
def extract min ( s e l f ) :
#find the root x with the minimum key
#case
#case
4
4
root
l i s t
of
in
the
heap
113 p = s e l f . head
114 x = None
115 p prev , x prev = None , None
116
117 if p is None:
118 return p 119 x = p
120 mini = p. key
121 p prev = p
122 p = p. sibling
123 while p is not None: 124 if p. key < mini :
125 x prev = p prev
126 x = p
127 mini = p. key
128 p prev = p
129 p = p. sibling
130 if x == s e l f . head :
131 s e l f . head = x . sibling 132 elif x . sibling is None: 133 xprev . sibling = None 134 else :
135 xprev . sibling = x . sibling
136 childx = x . child
137
138#i f the minimum node has no child 139 if child x is not None:
140””” i f the node has subtree , then insert them into a
new heap ,
141and union this new heap with old”””
142h = s e l f . makeheap ()
143 child x .p = None
144h. head = childx
145p = child x . sibling
146child x . sibling = None 147while p is not None:
148p prev = p
149p = p. sibling
150p prev . sibling = h. head
151 h. head = p prev
152p prev .p = None
153s e l f = s e l f . union ( self , h)
154return s e l f
155
156 def decrease key ( self , x , k) :
157if k > x . key :
158 print(”new key is greater than current key”)
159return
160
161x . key = k
162y = x
163z = y .p
164
165while z is not None and y . key < z . key :
166#do exchange
167#i f y and z have s a t e l l i t e fields , exchange them , too
168y . key = z . key
169z . key = k
170 y = z
171 z = y .p
172
173 def search ( self , k) :
174 x = s e l f . head
175 while x is not None: 176 if x . key == k : 177 return x 178 else :
179 if x . key < k and x . child is not None:
180 x = x . child
181 elif x . key > k or x . child is None:
182while x . sibling is None:
183x = x .p
184if x is None:
185return None
186x = x . sibling
187return None
188
189def delete ( self , x) :
190 s e l f . decrease key (x , −float ( ’ inf ’ ) )
191 return s e l f . extract min ()
192
193def test () :
194print(”BinomialHeaptest :\n”)
195#1. make heap test
196 print(”1. make heap test ”) 197 heap = binomialHeap () . make heap () 198if heap :
199 print(”make heap successfully \n”)
200
201#2. insert test
202 print(”2. insert test ”)
203heap = heap . insert (5)
204heap = heap . insert (8)
205heap = heap . insert (2)
206heap = heap . insert (7)
207heap = heap . insert (6)
208heap = heap . insert (9)
209heap = heap . insert (4) 210if heap . head is not None:
211 print(” insert to heap successfully \n”)
212
213#3. search key test
214print(”3. search key test ”)
215 key = 2
216 print(”find key” , key)
217 node = heap . search (key) 218 if node is not None:
219 print(node . key , ” is in the binomial heap”)
220 print(”search key successfully \n”) 221 else :
222 print(”Cannot find the key” , key , ”\n”)
223
224 #4. minimum key test
225 print(”4. minimum key test ”)
226 print(”The minimum: ” , heap .minimum() . key)
227print(”minimum key successfully \n”)
228
229#5. extract−min test
230 print(”5. extract−min test ”)
231heap = heap . extract min ()
232 print(”After extract−min , the minimum: ” , heap .minimum() . key)
233node = heap . search (key) 234if node is None:
235print(”After extract−min , the old minimum” , key , ” is in the heap”)
236 print(”exctract−min successfully \n”)
237
238#6. decrease key test
239 print(”6. decrease key test ”)
240key = 9
241decrease = 2
242print(”we are going to decrease the key” , key , ”to” ,
243node = heap . search (key)
244#make sure the key we want to decrease exist 245if node is not None:
246 print(node . key , ” is in the binomial heap”)
247heap . decreasekey (node , decrease ) 248else :
249print(”Cannotfind the key” , key)
250#check the update value exist
251node1 = heap . search (key)
252node2 = heap . search ( decrease )
253if node1 is None and node2 is not None:
254print(” after decrease key , ” , node2 . key , ” is in the binomial heap and” , key , ” is not in the binomial heap”) 255print(”decrease key successfully \n”) 256else :
257print(”decrease key is not successfully \n”)
258
259 #7. delete key test
260 print(”7. delete key test ”)
261 print(”before delete : ”)
262 delete = 7
node = heap . search ( delete )
if node is not None: print( delete , ” is in the binomial heap”) heap . delete (node)
else :
print( delete , ” is not in the binomial heap”)
print(” after delete : ”) node = heap . search ( delete )
if node is None: print( delete , ” is not in the binomial heap”) print(” delete
else :
print(” delete successfully \n”)
if name == ’ main
test ()
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
