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

Dưới đây là bài giảng Phân tích thiết kế giải thuật: Chương 5 - Heap nhị thức. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về các heap hợp nhất được; thời gian chạy của các thao tác lên heaps hợp nhất được; định nghĩa cây nhị thức; đặc tính của cây nhị thức; tính chất của heap nhị thức và một sô kiến thức khác.
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 5 - ĐH Bách khoa Cácheaphợpnhấtđược° Mộtheaphợpnhấtđược(mergeableheap)làmộtcấutrúcdữliệuhỗ trợnămthaotácsau(gọilàcácthaotácheaphợpnhấtđược). – MAKEHEAP()tạovàtrảvềmộtheaptrống. – INSERT(H,x)chènnútx,màtrườngkeycủanóđãđượcđiền,vào heapH. – MINIMUM(H)trảvềmộtcontrỏchỉđếnnúttrongheapHmàkhóa củanólànhỏnhất. – EXTRACTMIN(H)táchranútcókhóanhỏnhấtkhỏiH,vàtrảvề mộtcontrỏchỉđếnnútđó. – UNION(H1,H2)tạovàtrảvềmộtheapmớichứatấtcảcácnútcủa cácheapsH1vàH2.CácheapsH1vàH2sẽbịhủybởithaotácnày.7.3.2004 Chương5:Heapnhịthức 1 Thờigianchạycủacácthaotáclênheapshợpnhấtđược° nlàsốnútcủaheap Thủtục heap heap heap nhịphân nhịthức Fibonacci (worstcase) (worstcase) (khấuhao) MAKEHEAP (1) (1) (1) INSERT (lgn) O(lgn) (1) MINIMUM (1) O(lgn) (1) EXTRACTMIN (lgn) (lgn) O(lgn) UNION (n) O(lgn) (1) DECREASEKEY (lgn) (lgn) (1) DELETE (lgn) (lgn) O(lgn)7.3.2004 Chương5:Heapnhịthức 2 Heapnhịthức° Cácthaotáckhác – DECREASEKEY(H,x,k)gánvàonútxtrongheapHtrịmớikcủa khóa,knhỏhơnhaybằngtrịhiệnthờicủakhóa. – DELETE(H,x)xóanútxkhỏiheapH.° Nhậnxét: – HeapnhịthứckhônghổtrợthaotácSEARCHhữuhiệu. – Dođó,cácthaotácDECREASEKEYvàDELETEcầnmộtcontrỏ đếnnútcầnđượcxửlý.7.3.2004 Chương5:Heapnhịthức 3 Địnhnghĩacâynhịthức7.3.2004 Chương5:Heapnhịthức 4 Địnhnghĩacâynhịthức° CâynhịthứcBkvớik=0,1,2,…làmộtcâycóthứtựđượcđịnh nghĩađệquy: – CâynhịthứcB0gồmmộtnútduynhất. – CâynhịthứcBkgồmhaicâynhịthứcBk1đượcliênkếtvớinhau theomộtcáchnhấtđịnh: ° Nútgốccủacâynàylàconbêntráinhấtcủanútgốccủacây kia.7.3.2004 Chương5:Heapnhịthức 5 Đặctínhcủacâynhịthức° Lemma(Đặctínhcủamộtcâynhịthức) CâynhịthứcBkcócáctínhchấtsau: 1.có2knút, 2.chiềucaocủacâylàk, k 3.cóđúngnútt i ạiđộsâuivớii=0,1,...,k 4.bậccủanútgốccủacâylàk,nólớnhơnbậccủamọinútkhác; ngoàiranếucácconcủanútgốcđượcđánhsốtừtráisangphảibằng k1,k2,...,0,thìnútconilàgốccủacâyconBi. k k! i i!(k i )!7.3.2004 Chương5:Heapnhịthức 6 Đặctínhcủacâynhịthức Chứngminh Dùngquynạptheok. Bướccơbản:dễdàngthấycáctínhchấtlàđúngchoB0 Bướcquynạp:giảsửlemmalàđúngchoBk1. 1.CâynhịthứcBkgồmhaiBk1nênBkcó2k1+2k1=2knút. 2.DocáchliênkếthaicâynhịthứcBk1vớinhauđểtạonênBknên độsâutốiđacủanúttrongBkbằngđộsâutốiđacủanúttrongBk1 cộngthêm1,tứclà:(k1)+1=k.7.3.2004 Chương5:Heapnhịthức 7 Đặctínhcủacâynhịthức Chứngminh(tiếp) 3.GọiD(k,i)làsốcácnúttạiđộsâuicủacâynhịthứcBk. Độsâui1 Độsâui Bk1 Bk1 D(k , i) D (k 1, i ) D (k 1, i 1) k 1 k 1 i i 1 k i7.3.2004 Chương5:Heapnhịthức 8 Đặctínhcủacâynhịthức Chứngminh(tiếp) 4.Sửdụnghìnhsau. ... B0 B2 B1 Bk2 Bk1 Bk17.3.2004 Chương5:Heapnhịthức 9 Đặctínhcủacâynhịthức° Hệluận Bậctốiđacủamộtnútbấtkỳtrongmộtcâynhịthứccónnútlà ...