Bài giảng Phân tích thiết kế giải thuật - Chương 6: Fibonacci Heaps

) 
11 n [ H ]  n [ H ]  1 
12 return z 
7.10.2004 
20 
Chương 6: Fibonacci Heaps 
Củng cố (consolidate) 
Thủ tục phụ: củng cố danh sách các gốc của một Fibonacci heap H 
liên kết mọi cặp gốc có cùng bậc thành một gốc mới cho đến khi mọi gốc có bậc khác nhau. 
C ONSOLIDATE ( H ) 
 1 for i  0 to D ( n [ H ]) 
 2 do A [ i ]  NIL 
 3 for mổi nút w trong danh sách các gốc của H 
 4 do x  w 
 5 d  degree [ x ] 
 6 while A [ d ]  NIL 
 7 do y  A [ d ] 
 8 if key [ x ] > key [ y ] 
 9 then tráo x  y 
10 F IB -H EAP -L INK ( H , y , x ) 
11 A [ d ]  NIL 
12 d  d + 1 
13 A [ d ]  x 
7.10.2004 
21 
Chương 6: Fibonacci Heaps 
Củng cố (consolidate) 
(tiếp) 
14 min [ H ]  NIL 
15 for i  0 to D ( n [ H ]) 
16 do if A [ i ]  NIL 
17 then thêm A [ i ] vào danh sách các gốc của H 
18 if min [ H ] = NIL or key [ A [ i ]] < key [ min [ H ]] 
19 then min [ H ]  A [ i ] 
7.10.2004 
22 
Chương 6: Fibonacci Heaps 
Liên kết hai gốc có cùng bậc 
Thủ tục C ONSOLIDATE liên kết các gốc có cùng bậc mãi cho đến khi mọi gốc có được sau đó đều có bậc khác nhau. 
Dùng thủ tục F IB -H EAP -L INK ( H , y , x ) để tách gốc y khỏi danh sách gốc của H , sau đó liên kết gốc y vào gốc x , gốc x và gốc y có cùng bậc. 
F IB -H EAP -L INK ( H , y , x ) 
1 đem y ra khỏi danh sách các gốc của H 
2 làm y thành con của x , tăng degree [ x ] 
3 mark [ y ]  FALSE 
7.10.2004 
23 
Chương 6: Fibonacci Heaps 
Thực thi F IB -H EAP -E XTRACT -M IN : ví dụ 
7.10.2004 
24 
Chương 6: Fibonacci Heaps 
Thực thi F IB -H EAP -E XTRACT -M IN : ví dụ (tiếp) 
7.10.2004 
25 
Chương 6: Fibonacci Heaps 
Chi phí thực sự của F IB -H EAP -E XTRACT -M IN 
Gọi H là Fibonacci heap ngay trước khi gọi F IB - H EAP - E XTRACT - M IN , số nút của H là n . 
Chi phí thực sự bao gồm: 
O ( D ( n )): vì có nhiều lắm là D ( n ) con của nút nhỏ nhất cần được xử lý bỡi: 
F IB - H EAP - E XTRACT - M IN 
các dòng 1-2 và 14-19 của C ONSOLIDATE 
O ( D ( n ) + t ( H )): vì khi gọi C ONSOLIDATE chiều dài của danh sách gốc nhiều lắm là D ( n ) + t ( H )  1, mà thời gian chạy vòng lặp for dòng 3-13 nhiều lắm là tỉ lệ với chiều dài của danh sách gốc này. 
Vậy chi phí thực sự của F IB - H EAP - E XTRACT - M IN là O ( D ( n ) + t ( H )). 
7.10.2004 
26 
Chương 6: Fibonacci Heaps 
Chi phí khấu hao của F IB -H EAP -E XTRACT -M IN 
Gọi H’ là Fibonacci heap sau khi gọi F IB - H EAP - E XTRACT - M IN lên H . 
Nhắc lại: hàm thế năng của H được định nghĩa là 
( H ) = t ( H ) + 2 m ( H ) 
Biết: 
chi phí khấu hao = chi phí thực sự + ( H’ )  ( H ) 
Đã tính: phí tổn thực sự của F IB - H EAP - E XTRACT - M IN là O ( D ( n ) + t ( H )). 
Sau khi gọi F IB - H EAP - E XTRACT - M IN lên H , số gốc (hay số cây) của H’ nhiều lắm là D ( n ) + 1, và không có nút nào được đánh dấu. Vậy 
( H’ ) = ( D ( n ) + 1) + 2 m ( H ). 
7.10.2004 
27 
Chương 6: Fibonacci Heaps 
Chi phí khấu hao của F IB -H EAP -E XTRACT -M IN 
(tiếp) 
Do đó chi phí khấu hao của F IB - H EAP - E XTRACT - M IN là 
O ( D ( n ) + t ( H )) + ( ( D ( n ) + 1) + 2 m ( H ))  ( t ( H ) + 2 m ( H )) 
= O ( D ( n )) + O ( t ( H ))  t ( H ) 
= O ( D ( n )) , 
vì có thể scale up đơn vị của thế năng để khống chế hằng số ẩn trong O ( t ( H )). 
(Ví dụ: với O ( t ( H )) = 99 t ( H ) + 77 thì có thể chọn 1 đơn vị thế năng = 78 ) 
đến từ thế năng 
7.10.2004 
28 
Chương 6: Fibonacci Heaps 
Giảm khóa của một nút 
Thủ tục để giảm khóa của một nút: 
F IB -H EAP -D ECREASE -K EY 
giảm khóa của nút x trong Fibonacci heap H thành trị mới k nhỏ hơn trị cũ của khóa. 
F IB -H EAP -D ECREASE -K EY ( H , x , k ) 
1 if k > key [ x ] 
2 then error “khóa mới lớn hơn khóa hiện thời” 
3 key [ x ]  k 
4 y  p [ x ] 
5 if y  NIL and key [ x ] < key [ y ] 
6 then C UT ( H , x , y ) 
7 C ASCADING -C UT ( H , y ) 
8 if key [ x ] < key [ min [ H ]] 
9 then min [ H ]  x 
7.10.2004 
29 
Chương 6: Fibonacci Heaps 
Giảm khóa của một nút (tiếp) 
Thủ tục phụ để cắt liên kết giữa x và y , cha của nó, sau đó làm x thành một gốc. 
C UT ( H , x , y ) 
1 đem x ra khỏi danh sách các con của y , giảm degree [ y ] 
2 thêm x vào danh sách các gốc của H 
3 p [ x ]  NIL 
4 mark [ x ]  FALSE 
7.10.2004 
30 
Chương 6: Fibonacci Heaps 
Giảm khóa của một nút (tiếp) 
Thủ tục phụ để xử lý cha của nút bị cắt dựa trên trường mark [ x ]. 
C ASCADING -C UT ( H , y ) 
1 z  p [ y ] 
2 if z  NIL 
3 then if mark [ y ] = FALSE 
4 then mark [ y ]  TRUE 
5 else C UT ( H , y , z ) 
6 C ASCADING -C UT ( H , z ) 
7.10.2004 
31 
Chương 6: Fibonacci Heaps 
Giảm khoá của một nút: ví dụ 
(a) Heap ban đầu 
(b) Giảm khóa 46 thành 15 
(c)-(e) Giảm khóa 35 thành 5 
7.10.2004 
32 
Chương 6: Fibonacci Heaps 
Chi phí thực sự của F IB -H EAP -D ECREASE -K EY 
Gọi H là Fibonacci heap ngay trước khi gọi F IB - H EAP - D ECREASE - K EY, số nút của H là n . 
Chi phí thực sự của F IB - H EAP - D ECREASE - K EY bao gồm: 
O (1): dòng 1-5 và 8-9, 
thời gian thực thi các cascading cuts. Giả sử C ASCADING -C UT được gọi đệ quy c lần. Thời gian thực thi C ASCADING -C UT là O (1) không kể các gọi đệ quy. 
c lần 
7.10.2004 
33 
Chương 6: Fibonacci Heaps 
Chi phí thực sự của F IB -H EAP -D ECREASE -K EY 
(tiếp) 
Vậy phí tổn thực sự của F IB - H EAP - D ECREASE - K EY là O ( c ). 
7.10.2004 
34 
Chương 6: Fibonacci Heaps 
Chi phí khấu hao của F IB -H EAP -D ECREASE -K EY 
Gọi H’ là Fibonacci heap sau khi gọi F IB - H EAP - D ECREASE -K EY lên H . 
Nhắc lại: hàm thế năng của H được định nghĩa là 
( H ) = t ( H ) + 2 m ( H ) 
chi phí khấu hao = chi phí thực sự + ( H’ )  ( H ) 
Đã tính: chi phí thực sự của F IB - H EAP - D ECREASE -K EY là O ( c ). 
Sau khi gọi F IB - H EAP - D ECREASE -K EY lên H , thì H’ có t ( H ) + c cây. 
( H’ )  ( H )  ( t ( H ) + c ) + 2( m ( H )  c + 2)  ( t ( H ) + 2 m ( H )) 
  4  c . 
số lần gọi CUT bằng số lần gọi C ASCADING -C UT = c , mà 
 mỗi lần thực thi CUT thì 1 nút trở thành cây 
 mỗi lần thực thi C ASCADING -C UT ngoại trừ lần cuối của gọi đệ 
 quy thì 1 nút được unmarked và lần cuối của gọi đệ quy 
 C ASCADING -C UT có thể marks 1 nút. 
7.10.2004 
35 
Chương 6: Fibonacci Heaps 
Chi phí khấu hao của F IB -H EAP -D ECREASE -K EY 
(tiếp) 
Do đó chi phí khấu hao của F IB - H EAP - D ECREASE -K EY là 
O ( c ) + 4  c = O (1), 
vì có thể scale up đơn vị của thế năng để khống chế hằng số ẩn trong O ( c ). 
đến từ thế năng 
7.10.2004 
36 
Chương 6: Fibonacci Heaps 
Xóa một nút 
Thủ tục để xóa một nút: 
F IB -H EAP -D ELETE 
Xóa một nút x khỏi một Fibonacci heap H . 
F IB -H EAP -D ELETE ( H , x ) 
1	F IB -H EAP -D ECREASE -K EY ( H , x ,  ) 
2	F IB -H EAP -E XTRACT -M IN ( H ) 
7.10.2004 
37 
Chương 6: Fibonacci Heaps 
Chận trên lên bậc lớn nhất 
Lemma (sách: Lemma 21.1) 
	Cho x là một nút bất kỳ trong một Fibonacci heap, và giả sử degree [ x ] = k . Gọi y 1 , y 2 ,..., y k là các con của x được xếp theo thứ tự lúc chúng được liên kết vào x , từ lúc sớm nhất đến lúc trễ nhất. Thì degree [ y 1 ]  0 và degree [ y i ]  i - 2 với i = 2, 3,..., k . 
... 
x 
y 1 
y 2 
y k 
7.10.2004 
38 
Chương 6: Fibonacci Heaps 
Chận trên lên bậc lớn nhất 
(tiếp) 
Chứng minh 
Rõ ràng là degree [ y 1 ]  0. 
i  2: 
Khi y i được liên kết vào x thì y 1 , y 2 ,..., y i - 1 là trong tập các con của x nên khi đó degree [ x ]  i - 1. 
Nút y i được liên kết vào x chỉ khi nào degree [ x ] = degree [ y i ], vậy khi đó degree [ y i ] cũng  i - 1. 
Kể từ khi đó đến nay, nút y i mất nhiều lắm là một con, vì nếu nó mất hai con thì nó đã bị cắt khỏi x . Vậy 
degree [ y i ]  ( i - 1) - 1 
  i - 2 . 
7.10.2004 
39 
Chương 6: Fibonacci Heaps 
Chận trên lên bậc lớn nhất (tiếp) 
Định nghĩa 
Với k = 0, 1, 2,... định nghĩa F k là s ố Fibonacci thứù k : 
Lemma (sách: Lemma 21.2, bài tập) 
	Với mọi số nguyên k  0, 
	 Lemma (Bài tập 2.2-8) 
	Với mọi số nguyên k  0, ta có F k + 2  f k , trong đó f = (1 + 5 ) / 2, tỉ số vàng . 
 0	nếu k = 0, 
 F k = 1	nếu k = 1, 
 F k - 1 + F k - 2 nếu k  2. 
7.10.2004 
40 
Chương 6: Fibonacci Heaps 
Chận trên lên bậc lớn nhất (tiếp) 
Lemma (sách: Lemma 21.3) 
	Cho x là một nút bất kỳ trong một Fibonacci heap, và cho k = degree [ x ]. Thì size( x )  F k + 2  f k , trong đó f = (1 + 5 ) / 2. 
	 Chứng minh 
Gọi s k là trị nhỏ nhất có thể được của size( z ) trên mọi nút z mà degree [ z ] = k . 
Rõ ràng là s 0 = 1, s 1 = 2, s 2 = 3. 
Ta có s k  size( x ) 
7.10.2004 
41 
Chương 6: Fibonacci Heaps 
Chận trên lên bậc lớn nhất 
	 Chứng minh (tiếp) 
vì s k là tăng đơn điệu theo k , nên từ degree [ y i ]  i - 2 (Lemma 21.1) ta có . Vậy 
... 
x  
y 1 
y 2 
y k 
7.10.2004 
42 
Chương 6: Fibonacci Heaps 
Chận trên lên bậc lớn nhất 
	 Chứng minh (tiếp) 
dùng quy nạp theo k để chứng minh rằng s k  F k + 2 , với k  0: 
Bước cơ bản: với k = 0 và k = 1 là rõ ràng. 
Bước quy nạp: 
Giả thiết quy nạp: k  2 và s i  F i + 2 với i = 0, 1,, k - 1. Từ trên ta có 
vậy: size( x )  s k  F k + 2  f k . 
7.10.2004 
43 
Chương 6: Fibonacci Heaps 
Chận trên lên bậc lớn nhất (tiếp) 
Hệ luận 
	Bậc lớn nhất D ( n ) của nút bất kỳ trong một Fibonacci heap có n nút là O (lg n ). 
	 Chứng minh 
	Dùng Lemma 21.3. 
7.10.2004 
44 
Chương 6: Fibonacci Heaps