›
›

Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 2: Các cấu trúc dữ liệu - Chương 11: Hàng ưu tiên

Download
Chöông 11 – Haøng öu tieân  
Chöông 11 – HAØNG ÖU TIEÂN  
Caáu truùc döõ lieäu haøng ñôïi maø chuùng ta ñaõ xem xeùt trong chöông 3 laø theo ñuùng  
nguyeân taéc FIFO. Tuy nhieân trong thöïc teá, coù nhöõng tröôøng hôïp caàn coù söï linh  
ñoäng hôn. Chaúng haïn trong soá caùc coâng vieäc caàn xöû lyù, coù moät soá ít coâng vieäc voâ  
cuøng quan troïng, chuùng caàn ñöôïc xöû lyù caøng sôùm caøng toát ngay khi coù theå. Hoaëc  
trong tröôøng hôïp coù nhieàu taäp tin cuøng ñang chôø ñöôïc in, moät soá taäp tin chæ coù 1  
trang trong khi moät vaøi taäp tin khaùc thì raát daøi. Neáu caùc taäp tin 1 trang ñöôïc in  
tröôùc thì khoâng aûnh höôûng ñeán thôøi gian chôø ñôïi cuûa caùc taäp tin khaùc bao nhieâu.  
Ngöôïc laïi, neáu cöù theo thöù töï FIFO, moät soá baûn in chæ coù 1 trang laïi phaûi chôø ñôïi  
quaù laâu.  
Haøng coù xeùt thöù töï öu tieân, hay goïi taét laø haøng öu tieân (priority queue), laø moät  
caùch giaûi quyeát caùc tröôøng hôïp treân moät caùch thoûa ñaùng. Tuøy vaøo öùng duïng, tieâu  
chí ñeå xeùt ñoä öu tieân do chuùng ta quyeát ñònh. Trong chöông naøy chuùng ta seõ ñaëc  
taû vaø hieän thöïc CTDL cho haøng öu tieân naøy.  
11.1. Ñònh nghóa haøng öu tieân  
Haøng öu tieân coù caùc phöông thöùc gaàn gioáng nhö moät haøng ñôïi thoâng duïng, chæ  
khaùc veà maët chieán löôïc:  
Ñònh nghóa: Moät haøng öu tieân caùc phaàn töû kieåu T goàm caùc phaàn töû cuûa T, keøm  
caùc taùc vuï sau:  
1. Taïo môùi moät ñoái töôïng haøng roãng.  
2. priority_append: Theâm moät phaàn töû môùi vaøo haøng, giaû söû haøng chöa ñaày  
(tuøy vaøo ñoä öu tieân cuûa phaàn töû döõ lieäu môùi noù seõ ñöôïc ñöùng ôû moät vò trí thích  
hôïp).  
3. priority_serve: Loaïi moät phaàn töû ra khoûi haøng, giaû söû haøng chöa roãng  
(phaàn töû bò loaïi laø phaàn töû ñeán löôït ñöôïc xem xeùt theo quy öôùc ñoä öu tieân ñaõ  
ñònh).  
4. priority_retrieve: Xem phaàn töû taïi ñaàu haøng (phaàn töû saép ñöôïc xem xeùt).  
11.2. Caùc phöông aùn hieän thöïc haøng öu tieân  
Giaû söû ñoä öu tieân laø söï keát hôïp bôûi ñoä öu tieân theo tieâu chí maø chuùng ta ñaõ  
choïn cuøng vôùi thöù töï xuaát hieän cuûa coâng vieäc. Khi ñöa vaøo haøng, moãi coâng vieäc seõ  
coù moät thoâng soá ñeå chöùa ñoä öu tieân naøy. Chuùng ta quy öôùc raèng ñoä öu tieân caøng  
nhoû thöù töï öu tieân caøng cao.  
Chuùng ta coù theå duøng DSLK ñôn ñeå hieän thöïc haøng öu tieân. Vieäc theâm vaøo  
luoân thöïc hieän ôû ñaàu danh saùch, vieäc laáy ra seõ phaûi duyeät laàn löôït heát danh saùch  
ñeå choïn phaàn töû coù ñoä öu tieân cao nhaát. Ngöôïc laïi, neáu khi theâm vaøo luoân giöõ  
283  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
danh saùch ñuùng thöù töï taêng daàn cuûa ñoä öu tieân, khi laáy ra chæ caàn laáy phaàn töû ñaàu  
danh saùch. Caû hai caùch ñeàu toán O(1) cho moät taùc vuï vaø O(N) cho taùc vuï coøn laïi.  
Phöông aùn thöù hai coù theå hieän thöïc haøng öu tieân bôûi moät caây nhò phaân tìm  
kieám (BST). Phöông aùn naøy caàn O(logN) cho moãi taùc vuï theâm hoaëc loaïi phaàn töû.  
Taùc vuï priority_serve seõ luoân laáy ra phaàn töû cöïc traùi cuûa caây nhò phaân, ñieàu  
naøy seõ laøm cho caây maát caân baèng vaø coù theå khaéc phuïc baèng caùch söû duïng caây AVL  
thay cho caây BST bình thöôøng.  
Tuy nhieân caùc phöông aùn söû duïng caây treân ñaây hôi bò thöøa. Vieäc quaûn lyù caây  
quaù phöùc taïp so vôùi muïc ñích cuûa chuùng ta.  
Caùch hieän thöïc ñôn giaûn vaø phoå bieán cho haøng öu tieân laø heap nhò phaân  
(binary heap), coù khi coøn ñöôïc goïi taét laø heap. Vaø vì noù khaù phoå bieán neân nhieàu  
luùc ngöôøi ta chæ goïi ñôn giaûn laø heap, chöù khoâng coøn goïi laø haøng öu tieân nöõa.  
Ñònh nghóa heap nhò phaân ñaõ ñöôïc trình baøy trong chöông 8. Trong chöông naøy  
chuùng ta söû duïng heapnhò phaân laø moät min-heap.  
Phaàn hieän thöïc moät CTDL heap cuï theå ñöôïc xem nhö baøi taäp. Phaàn tieáp sau  
ñaây trình baøy caùc thao taùc treân heap baèng maõ giaû, vaø ñeå deã daøng hình dung  
chuùng ta cuõng vaãn duøng hình aûnh cuûa caây nhò phaân ñeå minh hoïa.  
11.3. Hieän thöïc caùc taùc vuï cô baûn treân heapnhò phaân  
11.3.1.Taùc vuï theâm phaàn töû  
Ñeå theâm moät phaàn töû môùi vaøo heap, chuùng ta taïo moät choã troáng ngay sau  
phaàn töû cuoái cuûa heap, ñieàu naøy baûo ñaûm heap vaãn coù caáu truùc caây nhò phaân ñaày  
ñuû hoaëc gaàn nhö ñaày ñuû. Neáu phaàn töû môùi coù theå ñaët vaøo choã troáng naøy maø khoâng  
vi phaïm ñieàu kieän thöù hai cuûa heap (baèng caùch so saùnh phaàn töû môùi vôùi nuùt cha  
cuûa choã troáng naøy) thì giaûi thuaät keát thuùc. Ngöôïc laïi, chuùng ta laáy phaàn töû cha  
cuûa choã troáng naøy ñeå laáp vaøo choã troáng, luùc ñoù seõ xuaát hieän choã troáng môùi. Coâng  
vieäc laäp laïi töông töï cho ñeán khi tìm ñöôïc vò trí thích hôïp cho phaàn töû môùi.  
Hình 11.1 minh hoïa vieäc theâm phaàn töû 14 vaøo moät heap.  
Vieäc theâm phaàn töû môùi toán nhieàu nhaát laø O(logN).  
284  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
13  
13  
16  
16  
21  
21  
68  
68  
19  
19  
31  
24  
24  
26  
26  
31  
65  
32  
65  
32  
13  
13  
16  
14  
16  
68  
19  
21  
24  
68  
19  
21  
24  
26  
31  
65  
32  
26  
31  
65  
32  
Hình 11.1. Theâm phaàn töû 14 vaøo heap  
ErrorCode Priority_Queue::priority_append(Entry item)  
/*  
pre: ñoái töôïng Priority_Queue coù thuoäc tính heap laø maûng lieân tuïc chöùa caùc phaàn töû.  
post: item ñöôïc theâm vaøo haøng öu tieân sao cho tính chaát heapvaãn thoaû.  
*/  
{
1. if (full())  
1. return overflow;  
2. else  
1. current_position = size()  
2. loop ((toàn taïi parent laø cha cuûa phaàn töû taïi current_position) AND  
(parent > item)  
//Laàn löôït di chuyeån caùc nuùt cha xuoáng neáu cha lôùn hôn item ñeå laáp choã troáng  
1. heap[current_position] = parent  
2. Cho current_position laø vò trí cuûa parent  
3. endloop  
4. heap[current_position] = item  
5. // Caäp nhaät laïi kích thöôùc cuûa heap.  
6. return success  
3. endif  
}
285  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
11.3.2.Taùc vuï loaïi phaàn töû  
Vieäc loaïi phaàn töû cuõng töông töï vieäc theâm vaøo. Phaàn töû laáy ra chính laø phaàn  
töû taïi goác cuûa caây vì ñoù laø phaàn töû coù ñoä öu tieân cao nhaát. Vieäc coøn laïi laø giaûi  
quyeát cho choã troáng naøy. Trong hình 11.2 chuùng ta seõ thaáy quaù trình di chuyeån  
cuûa choã troáng. Moät trong hai phaàn töû con cuûa noù seõ di chuyeån laáp ñaày choã troáng.  
Phaàn töû nhoû nhaát trong hai phaàn töû con ñöôïc choïn ñeå thoûa ñònh nghóa cuûa heap.  
Cuoái cuøng, vôùi choã troáng khoâng coøn nuùt con thì ñöôïc laáp ñaày bôûi phaàn töû cuoái cuûa  
heap vì chuùng ta luoân bieát raèng ñaây laø caây nhò phaân ñaày ñuû hoaëc gaàn nhö ñaày ñuû,  
noù luoân chöùa caùc phaàn töû coù theå ñieàn vaøo moät maûng lieân tuïc töø traùi sang phaûi. Vaø  
thöïc söï chuùng ta cuõng hieän thöïc heap trong moät maûng lieân tuïc chöù khoâng phaûi  
caáu truùc caây coù con troû. Moïi thao taùc vôùi caùc chæ soá ñeå ñònh vò ñeán caùc phaàn töû  
cha, con, ñeàu raát nhanh choùng. Chuùng ta coù theå chaéc chaén raèng ñieàu kieän thöù hai  
trong ñònh nghóa cuûa heap cuõng khoâng bò vi phaïm khi dôøi phaàn töû cuoái baèng caùch  
naøy. Chi phí trong vieäc loaïi phaàn töû laø O(logN).  
13  
16  
16  
14  
14  
68  
68  
19  
19  
21  
21  
19  
19  
26  
31  
26  
31  
65  
32  
65  
32  
14  
14  
16  
19  
16  
68  
19  
21  
68  
19  
21  
19  
26  
31  
14  
65  
32  
26  
31  
14  
65  
32  
16  
19  
16  
19  
68  
19  
21  
26  
68  
19  
21  
26  
31  
65  
32  
31  
65  
32  
Hình 11.2. Loaïi moät phaàn töû ra khoûi heap  
286  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
ErrorCode Priority_Queue::priority_serve()  
/*  
pre: ñoái töôïng Priority_Queue coù thuoäc tính heap laø maûng lieân tuïc chöùa caùc phaàn töû.  
post: phaàn töû nhoû nhaát trong haøng öu tieân ñöôïc laáy ñi.  
*/  
{
1. if (empty())  
1. return underflow;  
2. else  
1. current_position = 0  
2. loop (phaàn töû taïi current_position coù con)//Laàn löôït di chuyeån caùc nuùt  
// con leân ñeå laáp choã troáng.  
1. child laø phaàn töû nhoû nhaát trong hai con  
2. child ñöôïc cheùp leân vò trí current_position  
3. Cho current_position laø vò trí cuûa childvöøa ñöôïc cheùp  
3. endloop  
4. heap[current_position] = heap[size()-1]  
5. // Caäp nhaät laïi kích thöôùc cuûa heap.  
6. return success  
3. endif  
}
11.4. Caùc taùc vuï khaùc treân heap nhò phaân  
11.4.1.Taùc vuï tìm phaàn töû lôùn nhaát  
Taùc vuï priority_retrievetruy xuaát phaàn töû beù nhaát trong min-heapcoù chi  
phí O(1). Ñoái vôùi vieäc tìm ra phaàn töû lôùn nhaát trong min-heap khoù khaên hôn.  
Tuy vaäy, chuùng ta cuõng khoâng phaûi duøng caùch tìm tuyeán tính treân toaøn boä heap,  
vì caùc phaàn töû trong heap luoân coù moät traät töï nhaát ñònh theo ñònh nghóa. Chuùng  
ta thaáy ngay raèng phaàn töû lôùn nhaát phaûi laø moät trong caùc nuùt laù, ñoù laø moät nöûa  
beân phaûi cuûa maûng lieân tuïc chöùa caùc phaàn töû cuûa heap.  
11.4.2.Taùc vuï taêng giaûm ñoä öu tieân  
Taïi thôøi ñieåm khi maø caùc coâng vieäc ñöôïc ñöa vaøo haøng öu tieân, moãi coâng vieäc  
ñeàu ñaõ ñöôïc xaùc ñònh ñoä öu tieân, vaø chæ soá naøy chính laø khoùa ñöôïc xöû lyù bôûi heap.  
Tuy nhieân, giaû söû trong khi caùc coâng vieäc ñang naèm trong haøng öu tieân ñeå chôø  
ñeán löôït ñöôïc cung caáp dòch vuï, ngöôøi ñieàu haønh muoán can thieäp vaøo thöù töï öu  
tieân naøy vì moät soá lyù do. Chaúng haïn coù moät coâng vieäc ñang phaûi chôø quaù laâu vaø coù  
moät yeâu caàu ñoät xuaát caàn thuùc ñaåy noù ñöôïc hoaøn thaønh sôùm hôn. Ngöôïc laïi ngöôøi  
ñieàu haønh cuõng coù theå muoán ñieàu chænh giaûm ñoä öu tieân moät coâng vieäc naøo khaùc.  
Nhöõng ñieàu naøy raát thöôøng xaûy ra neáu chuùng ta xeùt trong moät tình huoáng raèng,  
trong cheá ñoä phuïc vuï coù phaân chia thôøi gian, khi heát khoaûng thôøi gian quy ñònh,  
neáu coâng vieäc vaãn chöa thöïc hieän xong thì laïi phaûi quay laïi haøng ñôïi naèm chôø  
tieáp. Moãi coâng vieäc thöôøng phaûi ñôïi, ñöôïc phuïc vuï, ñôïi, ñöôïc phuïc vuï,… vaøi laàn nhö  
theá môùi keát thuùc. Nhö vaäy thì vieäc ngöôøi ñieàu haønh ñöôïc quyeàn can thieäp vaøo  
haøng ñôïi tuøy vaøo nhöõng tình theá cuï theå laø raát coù lôïi. Nhöõng coâng vieäc ñoâi khi do  
287  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
tính thieáu hieäu quaû, ñaõ söû duïng toång thôøi gian phuïc vuï quaù lôùn maø vaãn chöa keát  
thuùc, thöôøng bò giaûm ñoä öu tieân nhö moät hình thöùc phaït.  
Tröôùc heát chuùng ta caàn boå sung moät vaiø CTDL vaø moät vaøi haøm phuï trôï sao cho  
khi moät coâng vieäc ñöôïc ñöa vaøo haøng öu tieân chuùng ta luoân naém ñöôïc vò trí cuûa noù  
trong haøng öu tieân, keå caû khi noù bò dòch chuyeån do caùc thao taùc cuûa caùc taùc vuï  
theâm, loaïi,…Taát nhieân nhöõng boå sung naøy seõ ñöôïc ñoùng kín trong CTDL  
Priority_Heap cuûa chuùng ta. Sau ñoù, chuùng ta coù theå thieát keá hai taùc vuï  
decrease_key(position, delta) vaø increase_key(position, delta) cho  
pheùp giaûm hoaëc taêng khoùa cuûa phaàn töû taïi vò trí position trong heap moät löôïng  
delta. Khi giaûm hoaëc taêng nhö vaäy, chuùng ta chæ caàn xöû lyù dòch chuyeån phaàn töû  
naøy leân hoaëc xuoáng vò trí thích hôïp trong heap so vôùi giaù trò môùi cuûa khoùa, vieäc  
naøy raát deã daøng vaø gaàn gioáng vôùi nhöõng gì chuùng ta ñaõ laøm trong hai taùc vuï  
priority_appendvaø priority_serve.  
11.4.3.Taùc vuï loaïi moät phaàn töû khoâng ôû ñaàu haøng  
Chuùng ta cuõng coù theå boå sung theâm taùc vuï loaïi haún moät coâng vieäc ñang ñôïi  
trong haøng (khoâng phaûi laø phaàn töû ñang ôû ñaàu haøng vaø coù ñoä öu tieân cao nhaát)  
nhaèm ñaùp öùng yeâu caàu cuûa moät ngöôøi söû duïng naøo ñoù muoán ngöng khoâng thöïc  
hieän coâng vieäc nöõa. Taùc vuï delete(position) ñôn giaûn laø goïi  
decrease_key(position,  
priority_serve.  
delta)  
vôùi delta voâ cuøng lôùn roài goïi  
11.5. Moät soá phöông aùn khaùc cuûa heap  
Ñaëc tính chính yeáu cuûa heap laø traät töï giöõa caùc phaàn töû cha – con. Ñieàu  
naøy ñaùp öùng muïc ñích cuûa haøng öu tieân laø truy xuaát nhanh choùng phaàn töû nhoû  
nhaát. Heap nhò phaân khai thaùc tính naêng cuûa maûng lieân tuïc taïo hieäu quaû nhaát  
ñònh trong caùc thao taùc treân haøng öu tieân. Döôùi ñaây laø moät vaøi phöông aùn khaùc  
cuûa heap, chuùng khai thaùc caùc öu ñieåm cuûa caùc caùch hieän thöïc khaùc nhau.  
11.5.1.d-heaps  
Heap nhò phaân luoân phoå bieán khi ngöôøi ta caàn duøng ñeán haøng öu tieân. d-  
heaps hoaøn toaøn gioáng heap nhò phaân ngoaïi tröø moãi nuùt coù d chöù khoâng phaûi 2  
con. d caøng lôùn caøng lôïi cho pheùp theâm vaøo, ngöôïc laïi, trong pheùp loaïi boû phaàn töû  
beù nhaát, caàn phaûi chi phí trong vieäc so saùnh d phaàn töû con cuûa moät nuùt ñeå laáy  
phaàn töû nhoû nhaát ñaåy leân. Do ñoù d-heap thích hôïp vôùi caùc öùng duïng maø pheùp  
theâm vaøo ñöôïc thöïc hieän thöôøng xuyeân. Ngoaøi ra coøn phaûi tính ñeán chi phí trong  
vieäc ñònh vò caùc nuùt cha, nuùt con trong maûng lieân tuïc. Neáu d laø luõy thöøa cuûa 2 thì  
caùc pheùp nhaân, chia ñöôïc thöïc hieän bôûi pheùp dòch chuyeån bit raát tieän lôïi. Cuoái  
cuøng, töông töï B-tree, khi döõ lieäu quaù lôùn khoâng chöùa ñuû trong boä nhôù thì  
d-heapcuõng thích hôïp vôùi vieäc söû duïng theâm boä nhôù ngoaøi.  
288  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
1
3
2
7
5
13  
15  
6
4
10  
8
17  
9
11  
9
Hình 11.3 . d-heap  
Nhöôïc ñieåm cuûa caùc heap treân ñaây laø vieäc tìm kieám moät phaàn töû baát kyø hay  
vieäc troän hai heap vôùi nhau khoâng thích hôïp. Chuùng ta seõ xem xeùt moät soá caáu  
truùc phöùc taïp hôn nhöng raát thích hôïp cho pheùp troän.  
11.5.2.Heap leäch traùi (Leftist heap)  
Vieäc söû duïng maûng lieân tuïc nhö heap nhò phaân thaät khoâng deã ñeå thöïc hieän  
pheùp troän moät caùch hieäu quaû, vì noù luoân ñoøi hoûi vieäc di chuyeån caùc phaàn töû. Moïi  
CTDL thích hôïp cho vieäc troän ñeàu duøng ñeán con troû. Nhöôïc ñieåm cuûa con troû laø  
thôøi gian xaùc ñinh vò trí caùc phaàn töû laâu hôn so vôùi trong maûng lieân tuïc. Heap  
leäch traùi seõ söû duïng caáu truùc lieân keát vôùi caùc con troû traùi vaø phaûi taïi moãi nuùt ñeå  
chöùa ñòa chæ cuûa hai nuùt con, muïc ñích ñeå khai thaùc ñieåm maïnh cuûa pheùp troän.  
Heap leäch traùi cuõng gioáng vôùi heap nhò phaân ôû caáu truùc nhò phaân vaø traät töï  
giöõa caùc phaàn töû cha – con. Chuùng ta luoân nhôù raèng, traät töï giöõa caùc phaàn töû cha  
– con laø tính chaát cô baûn nhaát cuûa moïi heap. Ñieåm khaùc ôû ñaây laø heap leäch traùi  
khoâng coù söï caân baèng.  
Chuùng ta ñònh nghóa chieàu daøi ñöôøng ñi ñeán NULL cuûa moät phaàn töû X (null  
path length – Npl(X)) laø chieàu daøi cuûa ñöôøng ñi ngaén nhaát töø X ñeán moät nuùt laù.  
Npl cuûa nuùt laù vaø nuùt baäc moät baèng 0, Npl(NULL) = -1. Npl cuûa baát kyø nuùt naøo  
baèng Npl cuûa nuùt con coù Npl nhoû nhaát coäng theâm 1.  
Heap leäch traùi coù tính chaát sau ñaây: taïi moïi nuùt, Npl cuûa nuùt con traùi  
luoân lôùn hôn hoaëc baèng Npl cuûa nuùt con phaûi. Tính chaát naøy laøm cho heap  
leäch traùi maát caân baèng. Chuùng ta goïi ñöôøng ñi traùi (hoaëc phaûi) taïi moãi nuùt laø  
ñöôøng ñi ñeán nuùt döôùi cöïc traùi (cöïc phaûi) töông öùng cuûa nuùt ñoù. Moïi nuùt trong  
heap leäch traùi luoân coù khuynh höôùng coù ñöôøng ñi traùi daøi hôn ñöôøng ñi phaûi, do  
ñoù ñöôøng ñi phaûi taïi nuùt goác luoân laø ñöôøng ngaén nhaát trong caùc ñöôøng ñi töø goác  
ñeán caùc nuùt laù.  
Coù theå chöùng minh baèng suy dieãn raèng moät caây heap leäch traùi vôùi r nuùt treân  
ñöôøng ñi phaûi seõ coù ít nhaát 2r-1 nuùt. Töø ñoù caây heap leäch traùi N nuùt seõ coù nhieàu  
nhaát ⎣log(N+1)⎦ nuùt treân ñöôøng ñi phaûi. YÙ töôûng chính cuûa heap leäch traùi laø  
289  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
moïi taùc vuï ñeàu ñöôïc thöïc hieän treân ñöôøng ñi phaûi ñeå luoân ñöôïc baûo ñaûm vôùi chi  
phí log(N).  
1
1
0
1*  
0
1
1
0
0
0
0
0
0
(a)  
(b)  
Hình11.4. Npl taïi moãi nuùt.  
(a)- Thoaû ñieàu kieän heapleäch traùi.  
(b)- Nuùt coù daáu * vi phaïm ñieàu kieän heapleäch traùi..  
Caùc taùc vuï treân heap leäch traùi  
Taùc vuï cô baûn nhaát cuûa heap leäch traùi laø taùc vuï troän. Chuùng ta seõ thaáy pheùp  
theâm vaøo vaø pheùp loaïi boû ñöôïc thöïc hieän deã daøng nhôø goïi pheùp troän naøy.  
Ngoaøi hai con troû traùi vaø phaûi, moãi nuùt trong heapleäch traùi coøn coù theâm thoâng  
tin laø Npl cuûa noù.  
Ñeå troän hai heap leäch traùi H1 vaø H2:  
• Neáu moät trong hai heaproãng thì traû veà heapcoøn laïi.  
• Ngöôïc laïi, so saùnh döõ lieäu taïi hai nuùt goác, thöïc hieän troän heap coù goác lôùn  
hôn vôùi caây con phaûi cuûa heap coù goác nhoû hôn. Ñieàu naøy baûo ñaûm goác cuûa  
heap keát quaû luoân coù trò nhoû nhaát trong taát caû caùc nuùt, vì heap keát quaû coù  
goác chính laø goác cuûa heapban ñaàu coù goác nhoû hôn.  
Ñaây chính laø quaù trình ñeä quy. Tröôùc khi keát thuùc moät laàn goïi ñeä quy, chuùng  
ta chæ caàn kieåm tra nuùt goác naøy coù thoûa ñieàu kieän cuûa heap leäch traùi hay khoâng,  
neáu caàn chuùng ta chæ caàn hoaùn vò hai con traùi vaø phaûi cuûa noù ñeå coù ñöôïc Npl cuûa  
nuùt con traùi lôùn hôn hoaëc baèng Npl cuûa nuùt con phaûi. Npl cuûa nuùt goác ñöôïc caäp  
nhaät baèng Npl cuûa nuùt con phaûi coäng theâm 1.  
Hình 11.5 minh hoïa quaù trình troän hai heap leäch traùi H1 vaø H2.  
290  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
6
3
7
12  
8
10  
37  
18  
24  
18  
17  
14  
21  
33  
26  
23  
H1  
H2  
(a)- Do 6>3, troän H2 vôùi caây con goác 8.  
3
6
8
10  
7
17  
12  
14  
21  
37  
18  
26  
24  
18  
23  
33  
(b)- Do8>6, troän caây con goác 8 vôùi caây con goác 7.  
3
6
8
10  
7
14  
12  
17  
21  
37  
18  
18  
26  
24  
23  
33  
(c)-Do 8>7, troän caây con goác 8 vôùi caây con goác 18.  
3
6
10  
12  
7
14  
21  
37  
23  
24  
8
18  
18  
17  
33  
26  
(d)- Do 18>8, troän caây con goác 18 vôùi caây con phaûi cuûa 8 (NULL)  
291  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
3
6
10  
12  
7
14  
21  
37  
23  
24  
8
18  
18  
17  
33  
26  
(e)- Taïi nuùt 18 vaø nuùt 8 khoâng vi phaïm heap leäch traùi.  
3
6
10  
12  
7
14  
21  
37  
23  
24  
8
18  
18  
17  
33  
26  
(f)- Taïi nuùt 7 vi phaïm heap leäch traùi, hoaùn vò hai caây con.  
3
6
10  
12  
7
14  
21  
37  
23  
8
24  
18  
18  
17  
33  
26  
(g)- Taïi nuùt 6 khoâng vi phaïm heap leäch traùi.  
3
6
10  
12  
7
14  
21  
37  
23  
8
24  
18  
18  
17  
33  
26  
(h)- Taïi nuùt 3 vi phaïm heap leäch traùi, hoaùn vò hai caây con.  
Hình 11.5- Troän hai heap leäch traùi H1 vaø H2  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
292  
Chöông 11 – Haøng öu tieân  
//Phaàn maõ giaû cho khai baùo vaø moät soá taùc vuï cho LeftistHeap.  
struct LeftistHeap_Node  
DataType  
data  
LeftistHeap_Node* left  
LeftistHeap_Node* right  
int  
Npl  
end struct  
class Leftist_Heap  
public:  
void merge(ref Leftist_Heap H1, ref Leftist_Heap H2)  
private:  
LeftistHeap_Node* recursive_merge(ref LeftistHeap_Node* p1,  
ref LeftistHeap_Node* p2)  
LeftistHeap_Node* aux_merge(ref LeftistHeap_Node* p1,  
ref LeftistHeap_Node* p2)  
LeftistHeap_Node* root  
end class  
void Leftist_Heap::merge(ref Leftist_Heap H1, ref Leftist_Heap H2)  
/*  
post:H1 laø heap leäch traùi laø keát quaû troän hai heapH1 vaø H2, H2 roãng.  
*/  
{
1. recursive_merge(H1.root, H2.root);  
}
LeftistHeap_Node* Leftist_Heap::recursive_merge(ref LeftistHeap_Node* p1,  
ref LeftistHeap_Node* p2)  
/*  
pre: p1 vaø p2 laø ñóa chæ nuùt goác cuûa hai heapleäch traùi.  
post: Traû veà ñòa chæ nuùt goác cuûa heap leäch traùi laø keát quaû troän hai heap ban ñaàu, p1 vaø p2 laø  
NULL.  
uses:Söû duïng haøm aux_merge.  
*/  
{
LeftistHeap_Node* p;  
1. if (p1 == NULL)  
1. p = p2;  
2. if (p2 = NULL)  
1. p = p1;  
3. if (p1->data < p2->data)  
1. p = aux_merge(p1, p2);  
4. else  
1. p = aux_merge(p2, p1);  
5. p1 = NULL;  
6. p2 = NULL;  
7. return p;  
}
293  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
LeftistHeap_Node* Leftist_Heap::aux_merge(ref LeftistHeap_Node* p1,  
ref LeftistHeap_Node* p2)  
/*  
pre:p1vaø p2laø ñòa chæ nuùt goác cuûa hai heap leäch traùi.  
post: Heapp2ñöôïc troän vôùi caây con phaûi cuûa heap p1, p2gaùn veà NULL.  
uses: Söû duïng haøm SwapChildren vaø recursive_merge.  
*/  
{
1. if (p1->left == NULL) // Tröôøng hôïp naøy p1_>rightñaõ laø NULLdo ñieàu kieän  
1. p1->left = p2;  
2. else  
// cuûa heapleäch traùi.  
1. p1->right = recursive_merge(p1->right, p2);  
2. if(p1->left->Npl < p1->right->Npl)  
1. SwapChildren(p1); // Traùo 2 caây con cuûa p1.  
3. p1->Npl = p1->right->Npl + 1;  
3. return p1; // p2 ñaõ ñöôïc gaùn NULL trong recursive_merge.  
}
Thôøi gian troän hai heap leäch traùi tæ leä vôùi chieàu daøi cuûa ñöôøng ñi phaûi, vaø ñoù  
laø O(logN). Giaûi thuaät ñeä quy treân coù theå ñöôïc khöû ñeä quy nhö sau. Böôùc thöù  
nhaát thöïc hieän troän ñöôøng ñi phaûi cuûa hai heap, ñöôøng ñi phaûi cuûa heap keát quaû  
chính laø thöù töï taêng daàn cuûa caùc nuùt treân ñöôøng ñi phaûi cuûa hai heap ban ñaàu (3,  
6, 7, 8, 18). Keát quaû cho thaáy ôû hình 11.6. Böôùc thöù hai ñi laàn ngöôïc treân ñöôøng ñi  
phaûi cuûa caây keát quaû ñeå hoaùn vò caùc con traùi vaø con phaûi khi caàn thieát. Tröôøng  
hôïp chuùng ta vieäc hoaùn vò caàn thöïc hieän taïi nuùt 7 vaø nuùt 3.  
3
6
10  
12  
7
14  
21  
37  
23  
24  
8
18  
18  
17  
33  
26  
Hình 11.6. Keát quaû sau böôùc thöù nhaát cuûa giaûi thuaät troän khoâng ñeä quy.  
Pheùp theâm moät phaàn töû môùi chính laø pheùp troän heap leäch traùi ñaõ coù vôùi moät  
heap leäch traùi chæ coù duy nhaát nuùt caàn theâm vaøo. Pheùp loaïi phaàn töû nhoû nhaát cuûa  
heap leäch traùi laø pheùp laáy ñi phaàn töû taïi goác vaø troän hai caây con cuûa noù vôùi nhau.  
Nhö vaäy taát caû caùc taùc vuï treân heap leäch traùi ñeàu coù chi phí O(logN).  
294  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
11.5.3.Skew heap  
Skew heap gioáng nhö heap leäch traùi nhöng khoâng chöùa thoâng tin veà Npl vaø  
khoâng coù raøng buoäc gì veà chieàu daøi ñöôøng ñi phaûi. Nhö vaäy trong tröôøng hôïp xaáu  
nhaát caùc taùc vuï chi phí ñeán O(N), khi caây nhò phaân suy bieán thaønh chuoãi maéc  
xích N nuùt veà beân phaûi.  
Taùc vuï chính cuûa skew heap cuõng laø pheùp troän, trong ñoù vieäc hoaùn vò hai  
nhaùnh con luoân ñöôïc laøm. Taùc vuï naøy coù theå ñöôïc hieän thöïc ñeä quy hoaëc khoâng ñeä  
quy. Keát quaû vieäc hoaùn vò taïi taát caû caùc nuùt seõ laø ñöôøng ñi traùi cuûa heapcuoái cuøng  
seõ chöùa taát caû caùc nuùt treân hai ñöôøng ñi phaûi cuûa hai heapban ñaàu theo ñuùng thöù  
töï taêng daàn giuõa chuùng.  
3
6
10  
12  
7
14  
21  
37  
23  
8
24  
18  
18  
17  
33  
26  
Hình 11.7. Keát quaû troän H1 vaø H2 theo caùch cuûa skew heap, hoaùn vò hai con traùi vaø phaûi taïi  
moïi nuùt  
Nhö vaäy tuy tröôøng hôïp xaáu nhaát cuûa skew heap laø O(log N), nhöng skew  
heap coù öu ñieåm laø khoâng phaûi chi phí ñeå quaûn lyù Npl taïi moãi nuùt vaø cuõng khoâng  
phaûi so saùnh Npl ñeå qyeát ñònh coù hoaùn vò hai nuùt con taïi moãi nuùt hay khoâng.  
11.5.4.Haøng nhò thöùc (Binomial Queue)  
Haøng nhò thöùc laø moät phöông aùn hieän thöïc cuûa haøng öu tieân. Heapleäch traùi vaø  
skew heap thöïc hieän O(log N) moãi taùc vuï ñoái vôùi vieäc troän, theâm vaø loaïi phaàn  
töû nhoû nhaát. Heap nhò phaân thöïc hieän moãi taùc vuï theâm vaøo vôùi thôøi gian trung  
bình laø haèng soá. Haøng nhò thöùc trong tröôøng hôïp xaáu nhaát thöïc hieän O(logN)  
cho moãi taùc vuï, nhöng vieäc theâm vaøo cuõng coù thôøi gian trung bình laø haèng soá.  
Khaùc vôùi moïi hieän thöïc cuûa haøng öu tieân maø chuùng ta ñaõ xem xeùt, haøng nhò  
thöùc khoâng phaûi laø moät caây coù traät töï cuûa heap, maø laø moät röøng caùc caây coù traät töï  
cuûa heap, trong ñoù khoâng ñöôïc pheùp coù hai caây coù cuøng chieàu cao. Theo quy öôùc,  
caây coù chieàu cao 0 laø caây coù 1 nuùt; caây coù chieàu cao k coù ñöôïc baèng caùch noái moät  
caây chieàu cao k-1 vaøo nuùt goác cuûa moät caây chieàu cao k-1 khaùc. Hình 11.8 bieåu dieãn  
caùc caây coù chieàu cao laàn löôït laø 0, 1, 2, 3, 4. Töø hình veõ chuùng ta thaáy, caây Bk bao  
goàm moät nuùt goác vaø caùc caây con B0, B1,…, Bk-1. Caây Bk coù chính xaùc laø 2k nuùt, do ñoù  
295  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
töø ñaây chuùng ta seõ goïi caùc caây naøy laø caây nhò thöùc. Soá nuùt ôû möùc d trong caây nhò  
thöùc laø Cdk. Neáu moïi caây nhò thöùc trong haøng nhò thöùc ñeàu coù traät töï cuûa heap vaø  
khoâng cho pheùp coù nhieàu hôn moät caây nhò thöùc coù cuøng chieàu cao thì haøng öu tieân  
vôùi kích thöôùc baát kyø ñeàu coù theå ñöôïc bieåu dieãn bôûi moät haøng nhò thöùc nhö theá  
naøy. Chaúng haïn haøng öu tieân coù 13 nuùt seõ goàm caùc caây nhò thöùc B3, B2, vaø B0.  
Bieåu dieãn nhò phaân cuûa 13 chính laø 1101, ñieàu naøy hoaøn toaøn töông öùng vôùi söï coù  
maët cuûa B3, B2, vaø B0, maø khoâng coù maët cuûa B1.  
B0  
B1  
B2  
B3  
B4  
Hình 11.8- Hình daïng caùc caây nhò thöùc vôùi caùc chieàu cao 0, 1, 2, 3, vaø 4 ñöôïc quy ñònh trong  
haøng nhò thöùc.  
Hình 11.9 bieåu dieãn moät haøng nhò thöùc coù 6 nuùt.  
16  
12  
18  
21 24  
65  
Hình 11.9- Haøng nhò thöùc coù 6 nuùt.  
Phaàn töû nhoû nhaát trong haøng nhò thöùc chính laø moät trong caùc nuùt goác cuûa caùc  
caây nhò thöùc coù trong haøng. Do haøng nhò thöùc coù nhieàu nhaát laø log N caây nhò thöùc  
khaùc nhau, vieäc tìm kieám chi phí O(log N). Neáu chuùng ta ñaùnh daáu phaàn töû nhoû  
nhaát moãi khi coù söï thay ñoåi bôûi moät taùc vuï naøo thì chi phí naøy laø O(1).  
Pheùp troän trong haøng nhò thöùc raát deã daøng. Giaû söû chuùng ta caàn troän hai haøng  
nhò thöùc H1 vaø H2 trong hình 11.10. H3 laø haøng nhò thöùc keát quaû. Trong H1 vaø H2  
chæ coù moät caây nhò thöùc B0, vaäy B0 seõ laø moät thaønh phaàn cuûa H3. Chuùng ta keát  
hôïp hai caây nhò thöùc B1 trong H1 vaø H2 baèng caùch cho caây nhò thöùc coù goác lôùn hôn  
laøm caây con cuûa caây nhò thöùc coøn laïi. Vôùi caây nhò thöùc B2 vöøa coù ñöôïc vaø hai caây  
nhò thöùc B2 ban ñaàu trong H1 vaø H2, chuùng ta ñeå laïi moät caây trong H3, vaø keát hôïp  
296  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
hai caây B2 coøn laïi thaønh moät caây B3. Vì H3 chöa coù caây nhò thöùc B3 neân B3 cuoái  
cuøng naøy seõ laø thaønh phaàn cuûa H3.  
14  
23  
16  
12  
13  
26  
51 24  
18  
21 24  
65  
65  
H1  
H2  
Hình 11.10- Hai haøng nhò thöùc H1 vaø H2.  
14  
26 16  
18  
Hình 11.11 - Keát hôïp hai caây nhò thöùc B1 trong H1 vaø H2.  
12  
23  
13  
14  
21 24  
51 24  
26 16  
65  
65  
18  
Hình 11.12- Keát quaû troän H1 vaø H2 thaønh H3.  
Vieäc keát hôïp hai caây nhò thöùc toán O(1), vôùi O(log N)caây nhò thöùc trong moãi  
haøng nhò thöùc, vieäc troän hai haøng nhò thöùc cuõng toán O(log N) trong tröôøng hôïp  
xaáu nhaát. Ñeå taêng tính hieäu quaû, chuùng ta löu caùc caây nhò thöùc trong moãi haøng  
nhò thöùc theo thöù töï taêng daàn cuûa chieàu cao caùc caây.  
Vieäc theâm moät phaàn töû môùi vaøo haøng nhò thöùc töông töï nhö ñoái vôùi heap leäch  
traùi: troän haøng nhò thöùc coù duy nhaát phaàn töû caàn theâm vôùi haøng nhò thöùc ñaõ coù.  
Vieäc loaïi phaàn töû nhoû nhaát cuõng ñôn giaûn: tìm phaàn töû nhoû nhaát trong soá caùc  
nuùt goác cuûa caùc caây nhò thöùc. Giaû söû ñoù laø caây Bk. Sau khi loaïi boû nuùt goác cuûa caây  
Bk, chuùng ta coøn laïi caùc caây con cuûa noù: B0, B1,… Bk-1. Goïi röøng goàm caùc caây con  
naøy laø H’, vaø H’’ laø haøng nhò thöùc ban ñaàu khoâng keå BK. Vieäc cuoái cuøng caàn laøm laø  
troän H’ vaø H’’. Chuùng ta coù theå töï kieåm tra raèng caùc pheùp theâm vaø loaïi naøy ñeàu  
toán O(log N)trong tröôøng hôïp xaáu nhaát.  
297  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
23  
Chöông 11 – Haøng öu tieân  
1
1
3
1
2
3
2
1
1
2
2
1
1
3
1
4
5
3
5
2
3
2
3
2
4
4
1
1
2
3
2
4
4
1
1
6
7
5
7
5
5
2
3
2
3
6
4
4
4
1
1
5
2
3
2
3
6
6
4
Hình 11.13- Quaù trình theâm caùc phaàn töû 1, 2,…, 7 vaøo haøng nhò thöùc.  
298  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
23  
12  
13  
14  
21 24  
51 24  
26 16  
65  
65  
18  
H
23  
14  
21  
24  
13  
51 24  
26 16  
65  
65  
18  
H’’  
H’  
13  
23  
14  
21 24  
51 24  
26 16  
65  
65  
18  
Hình 11.14- Quaù trình loaïi phaàn töû nhoû nhaát trong haøng nhò thöùc H.  
Hieän thöïc cuûa haøng nhò thöùc  
Vieäc tìm phaàn töû nhoû nhaát caàn duyeät qua caùc goác cuûa caùc caây nhò thöùc trong  
haøng nhò thöùc (12, 23 vaø 13 trong hình 11.14). Chuùng ta coù theå duøng danh saùch  
lieân keát ñeå chöùa caùc nuùt goác naøy. Danh saùch seõ coù thöù töï theo chieàu cao cuûa caùc  
caây nhò thöùc ñeå phuïc vuï cho pheùp troän hai haøng nhò thöùc ñöôïc deã daøng.  
Töông töï, caùc nuùt con cuûa nuùt goác cuûa moät caây nhò thöùc cuõng ñöôïc chöùa trong  
moät danh saùch lieân keát (14, 24 vaø 21 trong hình 11.14), ñeå khi loaïi boû nuùt goác  
(nuùt 12) thì phaàn coøn laïi cuõng coù caáu truùc töông töï nhö moät haøng nhò thöùc môùi,  
raát thuaän lôïi trong pheùp loaïi phaàn töû nhoû nhaát trong haøng nhò thöùc.  
12  
23  
13  
14  
21 24  
51 24  
26 16  
65  
65  
18  
Hình 11.15- Haøng nhò thöùc H  
299  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
12  
21  
23  
51  
13  
14  
24  
24  
65  
16  
26  
65  
18  
Hình 11.16- Hieän thöïc lieân keát cuûa haøng nhò thöùc H.  
Trong hình veõ treân chuùng ta thaáy hình elipse neùt rôøi bieåu dieãn caùc danh saùch  
lieân keát caùc nuùt maø chuùng ta thöôøng phaûi duyeät qua. Hình elipse neùt rôøi lôùn chöùa  
caùc goác cuûa caùc caây nhò thöùc trong haøng nhò thöùc, khi caàn tìm phaàn töû nhoû nhaát  
trong haøng nhò thöùc chuùng ta tìm trong danh saùch naøy. Hình elipse neùt rôøi nhoû  
chöùa caùc nuùt con cuûa nuùt goác trong moät caây nhò thöùc.  
Trong quaù trình hình thaønh haøng nhò thöùc trong moät soá thao taùc döõ lieäu, khi  
keát hôïp hai caây nhò thöùc coù cuøng chieàu cao (hình 11.18), chuùng ta caàn noái moät  
trong hai caây thaønh caây con cuûa caây coøn laïi, maø caây con môùi naøy cuõng chính laø  
caây con coù chieàu cao lôùn nhaát so vôùi caùc caây con ñaõ coù. Vieäc cheøn caây con môùi vaøo  
ñaàu cuûa danh saùch lieân keát seõ thuaän tieän hôn, vì vaäy chuùng ta cho danh saùch naøy  
coù thöù töï giaûm daàn theo chieàu cao cuûa caùc caây con (hình 11.18).  
Ngoaøi ra, moãi nuùt trong caây nhò thöùc seõ coù moät con troû cho pheùp truy xuaát ñeán  
danh saùch caùc con cuûa noù. Toùm laïi, hieän thöïc ñôn giaûn vaø hieäu quaû cho haøng nhò  
thöùc thaät ñôn giaûn nhö hình 11.18, ñoù laø caáu truùc cuûa moät caây nhò phaân, moãi nuùt  
coù con troû traùi chæ ñeán nuùt con ñaàu tieân cuûa noù vaø con troû phaûi chæ ñeán nuùt anh  
em cuûa noù.  
12  
24  
23  
51  
13  
14  
24  
21  
65  
65  
16  
26  
18  
Hình 11.17- Goác caùc caây nhò thöùc ñöôïc chöùa trong maûng lieân tuïc.  
Hình 11.17 laø moät phöông aùn thay danh saùch lieân keát treân cuøng bôûi maûng lieân  
tuïc. Chuùng ta coù theå duøng maûng lieân tuïc caáp phaùt ñoäng ñeå khaéc phuïc nhöôïc ñieåm  
do khoâng bieát tröôùc chieàu cao cuûa caây nhò thöùc cao nhaát trong haøng nhò thöùc. Vieäc  
duøng maûng lieân tuïc cho pheùp tìm nhò phaân phaàn töû nhoû nhaát, tuy nhieân seõ laø  
laõng phí lôùn khi haøng nhò thöùc goàm quaù ít caây nhò thöùc vôùi nhieàu chieàu cao khaùc  
nhau.  
300  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
12  
12  
14  
14  
24  
21  
24  
21  
65  
16  
26  
16  
26  
65  
18  
18  
Hình 11.18- Keát hôïp hai caây nhò thöùc B2 thaønh moät caây nhò thöùc B3.  
Döôùi ñaây laø phaàn maõ giaû cho caùc khai baùo caáu truùc cuûa caây nhò thöùc vaø haøng  
nhò thöùc. Caùc taùc vuï keát hôïp hai caây nhò thöùc, troän hai haøng nhò thöùc, vaø loaïi  
phaàn töû nhoû nhaát trong haøng nhò thöùc cuõng ñöôïc trình baøy baèng maõ giaû.  
//Phaàn maõ giaû cho khai baùo vaø moät soá taùc vuï cho haøng nhò thöùc.  
struct Binomial_Node  
DataType  
data  
Binomial_Node* leftChild  
Binomial_Node* nextSibling  
end struct  
struct Binomial_Tree  
Binomial_Tree combineTrees(ref Binomial_Tree T1, ref Binomial_Tree T2)  
Binomial_Node* root  
int notEmpty() // Traû veà 1 neáu caây khoâng roãng, ngöôïc laïi traû veà 0.  
end struct  
class Binomial_Queue  
public:  
Binomial_Queue(Binomial_Node* p, int k)// k laø soá nuùt trong haøng nhò thöùc.  
int empty  
Binomial_Queue merge(ref Binomial_Queue H1, ref Binomial_Queue H2)  
protected:  
int count //Toång soá nuùt trong taát caû caùc caây nhò thöùc.  
Binomial_Tree Trees[MAX]  
end class  
Binomial_Tree Binomial_Tree::CombineTrees(ref Binomial_Tree T1,  
ref Binomial_Tree T2);  
/*  
pre: T1 vaø T2 khaùc roãng.  
post:T1 chöùa keát quaû keát hôïp hai caây T1 vaø T2, T2 roãng. Traû veà caây T1.  
*/  
{
1. if (T1.root->data > T2.root->data)  
1. Traùo T1 vaø T2 cho nhau  
2. T2.root->nextSibling = T1.root->leftChild // Cheøn caây T2vaøo ñaàu danh  
// saùch caùc caây con cuûa goác cuûa T1  
3. T1.root->leftChild = T2.root // Caäp nhaät nuùt con traùi cho nuùt goác cuûa T1  
4. T2.root = NULL  
5. return T1  
}
301  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Chöông 11 – Haøng öu tieân  
Binomial_Queue Binomial_Queue::merge(ref Binomial_Queue H1,  
ref Binomial_Queue H2)  
/*  
post: H1 chöùa keát quaû troän hai haøng nhò thöùc H1vaø H2, H2roãng. Traû veà haøng H1.  
uses: haøm Binomial_Tree::notEmpty()traû veà 1 neáu caây khoâng roãng, ngöôïc laïi traû veà 0.  
*/  
{
Binomial_Tree T1, T2, carry  
int i = 0  
1. H1.count = H1.count + H2.count  
2. loop (H2 chöa roãng hoaëc carry khoâng roãng)  
1. T1 = H1.Trees[i]  
2. T2 = H2.Trees[i]  
3. case (T1.notEmpty() + 2*T2.notEmpty() + 4*carry.notEmpty())  
1. case 0: // Khoâng coù caây naøo  
2. case 1: // Chæ coù caây T1  
1. break  
3. case 2: // Chæ coù caây T2  
1. H1.Trees[i] = T2  
2. H2.Trees[i].root = NULL  
3. break  
4. case 4: // Chæ coù caây carry  
1. H1.Trees[i] = carry  
2. carry.root = NULL  
3. break  
5. case 3: // Coù caây T1vaø T2  
1. carry = combineTrees(T1, T2)  
2. H1.Trees[i].root = NULL  
3. H2.Trees[i].root = NULL  
4. break  
6. case 5: // Coù caây T1vaø carry  
1. carry = combineTrees(T1, carry)  
2. H1.Trees[i].root = NULL  
3. break  
7. case 6:// Coù caây T2vaø carry  
1. carry = combineTrees(T2, carry)  
2. H2.Trees[i].root = NULL  
3. break  
8. case 7:// Coù caû 3caây T1, T2, vaø carry  
1. H1.Trees[i] = carry  
2. carry = combineTrees(T1, T2)  
3. H2.Trees[i].root = NULL  
4. break  
4. endcase  
5. i = i + 1  
3. endloop  
4. return H1  
}
302  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
Tải về để xem bản đầy đủ
pdf 22 trang baolam 25900 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 2: Các cấu trúc dữ liệu - Chương 11: Hàng ưu tiên", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfgiao_trinh_cau_truc_du_lieu_va_giai_thuat_phan_2_cac_cau_tru.pdf