Bài giảng Phân tích thiết kế giải thuật: Chương 6 - ĐH Bách khoa

Bài giảng Phân tích thiết kế giải thuật: Chương 6 - Fibonacci Heaps nêu lên cấu trúc của Fibonacci Heap; các thao tác lên Heap hợp nhất được; cây nhị thức không thứ tự; tạo một Fibonacci Heap mới; chèn một nút vào Fibonacci Heap; hợp nhất hai Fibonacci Heap;... Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật: Chương 6 - ĐH Bách khoa CấutrúccủaFibonacciheap• Địnhnghĩa• MộtFibonacciheaplàmộttậpcáccâymàmỗicâyđềulàheap ordered. – CâytrongFibonacciheapkhôngcầnthiếtphảilàcâynhịthức. – CâytrongFibonacciheaplàcógốcnhưngkhôngcóthứtự (unordered).14.3.2004 Chương6:FibonacciHeaps 1 CấutrúccủaFibonacciheap(tiếp)° HiệnthựcFibonacciheaptrongbộnhớ: Mỗinútxcó – p[x]:contrỏđếnnútchacủanó. – child[x]:contrỏđếnmộtconnàođótrongcácconcủanó. ° Cácconcủaxđượcliênkếtvớinhautrongmộtdanhsáchvòng liênkếtkép(circular,doublylinkedlist),gọilàdanhsáchcác concủax. ° Mỗiconytrongdanhsáchcácconcủaxcócáccontrỏ – left[y],right[y]chỉđếncácanhembêntráivàbênphảicủa y. Nếuylàconduynhấtcủaxthìleft[y]=right[y]=y.14.3.2004 Chương6:FibonacciHeaps 2 CấutrúccủaFibonacciheap(tiếp)° HiệnthựcFibonacciheaptrongbộnhớ(tiếp): Cáctrườngkháctrongnútx – degree[x]:sốcácconchứatrongdanhsáchcácconcủanútx – mark[x]:cótrịboollàTRUEhayFALSE, chỉrằngxcómấtmộtconhaykhôngkểtừlầncuốimàxđược làmthànhconcủamộtnútkhác.14.3.2004 Chương6:FibonacciHeaps 3 CấutrúccủaFibonacciheap(tiếp)° HiệnthựcFibonacciheaptrongbộnhớ(tiếp):• FibonacciheapH – TruycậpHbằngcontrỏmin[H]đếnnútgốccủacâychứakhoá nhỏnhấtgọilànútnhỏnhấtcủaH. ° NếuHlàtrốngthìmin[H]=NIL. – TấtcảcácnútgốccủacáccâytrongHđượcliênkếtvớinhaubỡi cáccontrỏleftvàrightcủachúngthànhmộtsáchliênkếtkép vònggọilàdanhsáchcácgốccủaH. – n[H]:sốcácnúthiệncótrongH.14.3.2004 Chương6:FibonacciHeaps 4 CấutrúccủaFibonacciheap:vídụ14.3.2004 Chương6:FibonacciHeaps 5 Hàmthếnăng° Dùngphươngphápthếnăngđểphântíchhiệusuấtcủacácthaotác lêncácFibonacciheap.° ChomộtFibonacciheapH – gọisốcáccâycủaFibonacciheapHlàt(H) – gọisốcácnútxđượcđánhdấu(mark[x]=TRUE)làm(H).• HàmthếnăngcủaHđượcđịnhnghĩanhưsau (H)=t(H)+2m(H) – thếnăngcủamộttậpcácFibonacciheaplàtổngcủacácFibonacci heapthànhphần.14.3.2004 Chương6:FibonacciHeaps 6 Hàmthếnăng(tiếp)° Khibắtđầuhàmthếnăngcótrịlà0,sauđóhàmthếnăngcótrị 0. Dođóchiphíkhấuhaotổngcộnglàmộtcậntrêncủachiphíthựcsự tổngcộngchodảycácthaotác.14.3.2004 Chương6:FibonacciHeaps 7 Bậctốiđa° GọiD(n)làcậntrênchobậclớnnhấtcủamộtnútbấtkỳtrongmột Fibonacciheapcónnút.° Sẽchứngminh:D(n)=O(lgn).14.3.2004 Chương6:FibonacciHeaps 8 Cácthaotáclênheaphợpnhấtđược° Nếuchỉdùngcácthaotáclênheaphợpnhấtđược: – MAKEHEAP – INSERT – MINIMUM – EXTRACTMIN – UNION• thìmỗiFibonacciheaplàmộttậpcáccâynhịthức“khôngthứtự”.14.3.2004 Chương6:FibonacciHeaps 9 Câynhịthứckhôngthứtự° Mộtcâynhịthứckhôngthứtự(unorderedbinomialtree)đượcđịnh nghĩađệquynhưsau – CâynhịthứckhôngthứtựU0gồmmộtnútduynhất. – MộtcâynhịthứckhôngthứtựUkđượctạobởihaicâynhịthức khôngthứtựUk1bằngcáchlấygốccủacâynàylàmcon(vịtrí trongdanhsáchcácconlàtùyý)củagốccủacâykia.° Lemma19.1đúngchocáccâynhịthứccũngđúngchocáccâynhịthức khôngthứtự,nhưngvớithayđổisauchotínhchất4: 4’.ĐốivớicâynhịthứckhôngthứtựUk,nútgốccóbậclàk,trịk lớnhơnbậccủamọinútbấtkỳkhác.Cácconcủagốclàgốccủacác câyconU0,U1,...,Uk1trongmộtthứtựnàođó.14.3.2004 Chương6:FibonacciHeaps 10 TạomộtFibonacciheapmới° ThủtụcđểtạomộtFibonacciheaptrống:• MAKEFIBHEAP – cấpphátvàtrảvềđốitượngFibonacciheapH,với n[H]=0, min[H]=NIL° PhântíchthủtụcMAKEFIBHEAP – ChiphíthựcsựlàO(1) – ThếnăngcủaFibonacciheaprỗnglà (H)=t(H)+2m(H) =0. – VậychiphíkhấuhaolàO(1).14.3.2004 Chương6:FibonacciHeaps 11 ChènmộtnútvàoFibonacciheap° ...