14.3.2004 Ch ng 6: Fibonacci Heapsươ 1
C u trúc c a Fibonacci heapấ ủ
•Đnh nghĩaị
•M t ộFibonacci heap là m t t p các cây mà m i cây đu là heap-ộ ậ ỗ ề
ordered.
–Cây trong Fibonacci heap không c n thi t ph i là cây nh th c.ầ ế ả ị ứ
–Cây trong Fibonacci heap là có g c nh ng không có th t ố ư ứ ự
(unordered).
14.3.2004 Ch ng 6: Fibonacci Heapsươ 2
C u trúc c a Fibonacci heap (ti p)ấ ủ ế
°Hi n th c Fibonacci heap trong b nh :ệ ự ộ ớ
M i nút ỗx có
–p[x]: con tr đn nút cha c a nó.ỏ ế ủ
–child[x]: con tr đn m t con nào đó trong các con c a nó.ỏ ế ộ ủ
°Các con c a ủx đc liên k t v i nhau trong m t danh sách vòng ượ ế ớ ộ
liên k t kép (circular, doubly linked list), g i là ế ọ danh sách các
con c a ủx.
°M i con ỗy trong danh sách các con c a ủx có các con trỏ
–left[y], right[y] ch đn các anh em bên trái và bên ph i c a ỉ ế ả ủ
y.
N u ếy là con duy nh t c a ấ ủ x thì left[y] = right[y] = y.
14.3.2004 Ch ng 6: Fibonacci Heapsươ 3
C u trúc c a Fibonacci heap (ti p)ấ ủ ế
°Hi n th c Fibonacci heap trong b nh (ti p):ệ ự ộ ớ ế
Các tr ng khác trong nút ườ x
–degree[x]: s các con ch a trong danh sách các con c a nút ố ứ ủ x
–mark[x]: có tr bool là ịTRUE hay FALSE,
ch r ng ỉ ằ x có m t m t con hay không k t l n cu i mà ấ ộ ể ừ ầ ố x đc ượ
làm thành con c a m t nút khác.ủ ộ
14.3.2004 Ch ng 6: Fibonacci Heapsươ 4
C u trúc c a Fibonacci heap (ti p)ấ ủ ế
°Hi n th c Fibonacci heap trong b nh (ti p):ệ ự ộ ớ ế
•Fibonacci heap H
–Truy c p ậH b ng con trằ ỏ min[H] đn nút g c c a cây ch a khoá ế ố ủ ứ
nh nh t g i làỏ ấ ọ nút nh nh t ỏ ấ c aủ H.
°N u ếH là tr ng thì ốmin[H] = NIL.
–T t c các nút g c c a các cây trong ấ ả ố ủ H đc liên k t v i nhau b i ượ ế ớ ỡ
các con tr ỏleft và right c a chúngủ thành m t sách liên k t kép ộ ế
vòng g i là ọdanh sách các g cố c a ủH.
–n[H]: s các nút hi n có trong ố ệ H.
14.3.2004 Ch ng 6: Fibonacci Heapsươ 5
C u trúc c a Fibonacci heap: ví dấ ủ ụ