Bài giảng Giải thuật - Chương 5: Các heap hợp nhất

Caùc heap hôïp nhaát ñöôïc

ª Heap nhò phaân

ª Moät heap hôïp nhaát ñöôïc (mergeable heap) laø moät caáu truùc döõ lieäu hoã

trôï naêm thao taùc sau (goïi laø caùc thao taùc heap hôïp nhaát ñöôïc).

– MAKE-HEAP() taïo vaø traû veà moät heap troáng.

– INSERT(H, x) cheøn nuùt x, maø tröôøng key cuûa noù ñaõ ñöôïc ñieàn, vaøo

heap H .

– MINIMUM(H) traû veà moät con troû chæ ñeán nuùt trong heap H maø

khoùa cuûa noù laø nhoû nhaát.

– EXTRACT-MIN(H) taùch ra nuùt coù khoùa nhoû nhaát khoûi H, vaø traû veà

moät con troû chæ ñeán nuùt ñoù.

– UNION(H₁, H₂) taïo vaø traû veà moät heap môùi chöùa taát caû caùc nuùt cuûa

caùc heaps H₁vaø H₂. Caùc heaps H₁vaø H₂seõ bò huûy bôûi thao taùc

naøy.

2.10.2004

1

Chöông 5: Heap nhò thöùc

Thôøi gian chaïy cuûa caùc thao taùc leân heaps hôïp nhaát ñöôïc

ª n laø soá nuùt cuûa heap

Thuû tuïc

heap

nhò phaân

(worst-case)

heap

nhò thöùc

Fibonacci

(worst-case)

(khaáu hao)

MAKE-HEAP

INSERT

MINIMUM

EXTRACT-MIN

UNION

DECREASE-KEY

DELETE

(1)

(lg n)

(1)

(lg n)

(n)

(lg n)

(1)

O(lg n)

(lg n)

O(lg n)

(lg n)

(1)

O(lg n)

(1)

O(lg n)

2.10.2004

2

Chöông 5: Heap nhò thöùc

Heap nhò thöùc

ª Heap nhò thöùc

Hoã trôï theâm caùc thao taùc

– DECREASE-KEY(H, x, k) gaùn vaøo nuùt x trong heap H trò môùi k cuûa

khoùa, k nhoû hôn hay baèng trò hieän thôøi cuûa khoùa.

– DELETE(H, x) xoùa nuùt x khoûi heap H.

ª Nhaän xeùt:

– Heap nhò thöùc khoâng hoå trôï thao taùc SEARCH höõu hieäu.

– Do ñoù, caùc thao taùc DECREASE-KEY vaø DELETE caàn moät con troû

ñeán nuùt caàn ñöôïc xöû lyù.

2.10.2004

3

Chöông 5: Heap nhò thöùc

Ñònh nghóa caây nhò thöùc

ª Caây nhò thöùc B_kvôùi k = 0, 1, 2,… laø moät caây coù thöù töï ñöôïc ñònh nghóa

ñeä quy:

– Caây nhò thöùc B₀goàm moät nuùt duy nhaát.

– Caây nhò thöùc B_kgoàm hai caây nhò thöùc B_{k - 1}ñöôïc lieân keát vôùi nhau

theo moät caùch nhaát ñònh:

°

Nuùt goác cuûa caây naøy laø con beân traùi nhaát cuûa nuùt goác cuûa caây

kia.

B₀

B_{k - 1}

B_k

2.10.2004

4

Chöông 5: Heap nhò thöùc

Ñònh nghóa caây nhò thöùc

ñoä saâu

0

1

2

3

4

B₀

B₁

B₂

B₄

B₃

2.10.2004

5

Chöông 5: Heap nhò thöùc

Ñaëc tính cuûa caây nhò thöùc

ª Lemma (Ñaëc tính cuûa moät caây nhò thöùc)

Caây nhò thöùc B_kcoù caùc tính chaát sau:

1. coù 2^knuùt,

2. chieàu cao cuûa caây laø k,

k

 

 

3. coù ñuùng

nuùt taïi ñoä saâu i vôùi i = 0, 1,..., k

 

i

 

4. baäc cuûa nuùt goác cuûa caây laø k, noù lôùn hôn baäc cuûa moïi nuùt khaùc;

ngoaøi ra neáu caùc con cuûa nuùt goác ñöôïc ñaùnh soá töø traùi sang phaûi baèng

k - 1, k - 2,..., 0, thì nuùt con i laø goác cuûa caây con B_i.

k

 

k!

 

=

i

i!(k - i)!

 

2.10.2004

6

Chöông 5: Heap nhò thöùc

Ñaëc tính cuûa caây nhò thöùc

Chöùng minh

Duøng quy naïp theo k.

Böôùc cô baûn: deã daøng thaáy caùc tính chaát laø ñuùng cho B₀

Böôùc quy naïp: giaû söû lemma laø ñuùng cho B_{k - 1}.

1. Caây nhò thöùc B_kgoàm hai B_{k - 1}neân B_kcoù 2^{k - 1}+ 2^{k - 1}= 2^knuùt.

2. Do caùch lieân keát hai caây nhò thöùc B_{k - 1}vôùi nhau ñeå taïo neân B_kneân

ñoä saâu toái ña cuûa nuùt trong B_kbaèng ñoä saâu toái ña cuûa nuùt trong B_{k - 1}

coäng theâm 1, töùc laø: (k - 1) + 1 = k.

2.10.2004

7

Chöông 5: Heap nhò thöùc

Ñaëc tính cuûa caây nhò thöùc

Chöùng minh (tieáp)

3. Goïi D(k, i) laø soá caùc nuùt taïi ñoä saâu i cuûa caây nhò thöùc B_k.

Ñoä saâu i

Ñoä saâu i - 1

B_{k - 1}

D(k,i) = D(k -1,i) + D(k -1,i -1)

k -1

i -1



 





 

+



=

 

i



 



k

 

 

i

 

2.10.2004

8

Chöông 5: Heap nhò thöùc

Ñaëc tính cuûa caây nhò thöùc

Chöùng minh (tieáp)

4. Söû duïng hình sau.

...

B₀

B₁

B₂

B_{k - 2}

B_{k - 1}

2.10.2004

9

Chöông 5: Heap nhò thöùc

Ñaëc tính cuûa caây nhò thöùc

ª Heä luaän

Baäc toái ña cuûa moät nuùt baát kyø trong moät caây nhò thöùc coù n nuùt laø lg n.

2.10.2004

10

Chöông 5: Heap nhò thöùc

Ñònh nghóa heap nhò thöùc

ª Ñònh nghóa

Moät heap nhò thöùc H laø moät taäp caùc caây nhò thöùc thoûa caùc tính chaát

heap nhò thöùc sau

1. Moïi caây nhò thöùc trong H laø heap-ordered: moïi nuùt ñeàu coù khoùa

lôùn hôn hay baèng khoùa cuûa nuùt cha cuûa noù.

2. Vôùi moïi soá nguyeân k  0 cho tröôùc thì coù nhieàu nhaát moät caây nhò

thöùc trong H maø goác cuûa noù coù baäc laø k.

2.10.2004

11

Chöông 5: Heap nhò thöùc

Tính chaát cuûa heap nhò thöùc

ª Tính chaát

1. Goác cuûa moät caây trong moät heap nhò thöùc chöùa khoùa nhoû nhaát

trong caây.

2. Moät heap nhò thöùc H vôùi n nuùt goàm nhieàu laém laø lg n + 1 caây

nhò thöùc.

Chöùng minh

1. Hieån nhieân.

2. n coù bieåu dieãn nhò phaân duy nhaát, bieåu dieãn naøy caàn lg n + 1

bits, coù daïng b _{lg n}, b _{lg n - 1},..., b₀ sao cho

3

2

1

0

lg n





n = b 2ⁱ

10 =

1 0 1 0



i

i=0

Cuøng vôùi ñònh nghóa 2, ta thaáy caây nhò thöùc B_ixuaát hieän trong H

neáu vaø chæ neáu b_i= 1.

2.10.2004

12

Chöông 5: Heap nhò thöùc

Bieåu dieãn heap nhò thöùc

moät caây nhò thöùc

“beân traùi laø con,

beân phaûi laø anh em”

2.10.2004

13

Chöông 5: Heap nhò thöùc

Bieåu dieãn heap nhò thöùc

Qui taéc tröõ cho moãi caây nhò thöùc trong moät heap nhò thöùc:

– bieåu dieãn theo kieåu “Beân traùi laø con, beân phaûi laø anh em” (left-

child, right-sibling representation)

ª Moãi nuùt x coù moät tröôøng sau:

– key[x]: tröõ khoùa cuûa nuùt.

ª Moãi nuùt x coù caùc con troû sau:

– p[x]: tröõ con troû ñeán nuùt cha cuûa x.

– child[x]: con troû ñeán con beân traùi nhaát cuûa x.

°

Neáu x khoâng coù con thì child[x] = NIL

– sibling[x]: con troû ñeán anh em cuûa x ôû ngay beân phaûi x.

Neáu x laø con beân phaûi nhaát cuûa cha cuûa noù thì sibling[x] = NIL.

°

2.10.2004

14

Chöông 5: Heap nhò thöùc

Bieåu dieãn heap nhò thöùc (tieáp)

ª Ngoaøi ra moãi nuùt x coøn coù moät tröôøng sau

– degree[x]: baäc cuûa x (= soá caùc con cuûa x)

ª Caùc goác cuûa caùc caây nhò thöùc trong moät heap nhò thöùc ñöôïc toå chöùc

thaønh moät danh saùch lieân keát, goïi laø danh saùch caùc goác cuûa heap nhò

thöùc.

– Khi duyeät danh saùch caùc goác cuûa moät heap nhò thöùc thì caùc baäc

cuûa caùc goác theo thöù töï taêng daàn.

– Neáu x laø moät goác thì sibling[x] chæ ñeán goác keá ñeán trong danh

saùch caùc goác.

ª Ñeå truy caäp moät heap nhò thöùc H

– head[H]: con troû chæ ñeán goác ñaàu tieân trong danh saùch caùc goác cuûa

H.

°

head[H] = NIL neáu H khoâng coù phaàn töû naøo.

2.10.2004

15

Chöông 5: Heap nhò thöùc

Taïo moät heap nhò thöùc

ª Thuû tuïc ñeå taïo moät heap nhò thöùc môùi:

MAKE-BINOMIAL-HEAP

– chieám choå cho vaø traû veà moät ñoái töôïng H vôùi head[H] = NIL.

– coù thôøi gian chaïy laø (1).

2.10.2004

16

Chöông 5: Heap nhò thöùc

Tìm khoùa nhoû nhaát

ª Thuû tuïc ñeå tìm khoùa nhoû nhaát trong moät heap nhò thöùc H coù n nuùt:

BINOMIAL-HEAP-MINIMUM

– traû veà moät con troû ñeán nuùt coù khoùa nhoû nhaát.

BINOMIAL-HEAP-MINIMUM(H)

1 y  NIL

2 x  head[H]

3 min  

4 while x  NIL

5

6

7

8

do if key[x] < min

then min  key[x]

y  x

x  sibling[x]

9 return y

– Thôøi gian chaïy cuûa thuû tuïc laø O(lg n) vì caàn kieåm tra nhieàu laém laø

lg n + 1 nuùt goác.

2.10.2004

17

Chöông 5: Heap nhò thöùc

Lieân keát hai caây nhò thöùc

ª Thuû tuïc ñeå lieân keát hai caây nhò thöùc:

BINOMIAL-LINK

– lieân keát caây nhò thöùc B_{k - 1}coù goác taïi nuùt y vaøo caây nhò thöùc B_{k - 1}

coù goác taïi nuùt z ñeå taïo ra caây nhò thöùc B_k. Nuùt z trôû neân goác cuûa

moät caây B_k.

BINOMIAL-LINK(y, z)

1 p[y]  z

2 sibling[y]  child[z]

3 child[z]  y

4 degree[z]  degree[z] + 1

– Thôøi gian chaïy cuûa thuû tuïc laø O(1).

2.10.2004

18

Chöông 5: Heap nhò thöùc

Hoøa nhaäp hai heap nhò thöùc

ª Thuû tuïc ñeå hoøa nhaäp (merge) danh saùch caùc goác cuûa heap nhò thöùc

H₁vaø danh saùch caùc goác cuûa heap nhò thöùc H₂:

BINOMIAL-HEAP-MERGE(H₁, H₂)

– hoøa nhaäp caùc danh saùch caùc goác cuûa H₁vaø H₂thaønh moät danh

saùch caùc goác duy nhaát maø caùc baäc coù thöù töï taêng daàn.

– neáu caùc danh saùch caùc goác cuûa H₁vaø H₂coù toång coäng laø m goác,

thì thôøi gian chaïy cuûa thuû tuïc laø O(m).

2.10.2004

19

Chöông 5: Heap nhò thöùc

Hôïp hai heap nhò thöùc

ª Thuû tuïc ñeå hôïp hai heap nhò thöùc:

BINOMIAL-HEAP-UNION

– hôïp nhaát hai heap nhò thöùc H₁vaø H₂vaø traû veà heap keát quaû.

BINOMIAL-HEAP-UNION(H₁, H₂)

1 H  MAKE-BINOMIAL-HEAP()

2 head[H]  BINOMIAL-HEAP-MERGE(H₁, H₂)

3 traû laïi caùc ñoái töôïng H₁vaø H₂nhöng giöû laïi caùc danh saùch maø

chuùng chæ vaøo

4 if head[H] = NIL

5

then return H

6 prev-x  NIL

7 x  head[H]

8 next-x  sibling[x]

2.10.2004

20

Chöông 5: Heap nhò thöùc