Sắp xếp vung đống (Heapsort) và 1 số ứng dụng

Một nút lá có thể được coi là một cây con đã thoả mãn tính chất của đống rồi .Như vậy tạo nên tạo đống hay vun đống có thể tiến hành theo kiểu từ đáy lên (botom-up) và bài toán này sẽ được quy về một phép xử lý chung như sau: chuyển đổi thành đống cho một cây mà con trái và con phải đã là đống rồi .Do đó ta cần xây dung thủ tục ADJUST nhằm thực hiện công việc này . Đối với cây nhị phân hoàn chỉnh có n nút thì nút ứng với chỉ số từ [n/2] trở xuống mới trở thành cha của nút khác nên khi tạo đống ADJUST chỉ áp đặt với nút vào với các cây mà gốc mà gốc của nó ứng với chỉ số [n/2] , [n/2] -1, , 1.Còn vơI vun đống thì lại đơn giản hơn . thủ tục ADJUST luôn luôn áp đặt vào cây mà gốc của nó bao giờ cũng là nút đầu tiên (ứng với chỉ số 1).Vì vậy ta cần đến hai thủ tục : thủ tục ADJUST và thủ tục HEAPSORT . ADJUST coi như một chương trình con được gọi tới trong HEAPSORT.

doc16 trang | Chia sẻ: lvcdongnoi | Ngày: 29/06/2013 | Lượt xem: 1908 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu Sắp xếp vung đống (Heapsort) và 1 số ứng dụng, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
®Ò thùc tËp S¾p xÕp vun ®èng (Heapsort)vµ mét sè øng dông Néi dung: ThuËt to¸n s¾p xÕp vun ®èng C¸c øng dông: a) Bµi to¸n 1: X¸c ®Þnh xem cã bao nhiªu gi¸ trÞ kh¸c nhau trong m¶ng gåm n sè nguyªn d­¬ng . D÷ liÖu: File v¨n b¶n cã tªn DAYSO.TXT ghi n(n> 105 ) sè nguyªn . KÕt qu¶: §­a ra sè l­îng c¸c gi¸ trÞ kh¸c nhau trong file ®· cho vµ c¸c gi¸ trÞ t­¬ng øng theo thø tù gi¶m dÇn. b)Bµi to¸n 2: T×m k phÇn tö nhá nhÊt cña mét danh s¸ch gåm n phÇn tö : D÷ liÖu: File v¨n b¶n cã tªn THONGKE.TXT ghi d·y gåm n (n>106) sè thùc kh¸c nhau . KÕt qu¶: Víi mçi gi¸ trÞ k (k ≤ 1000 ) cÇn ®­a ra danh s¸ch k sè nhá nhÊt trong d·y sè cho trong file THONGKE.TXT theo thø tù gi¶m dÇn. LËp tr×nh: ThuËt to¸n s¾p xÕp vun ®èng Ch­¬ng tr×nh gi¶i c¸c bµi to¸n Ng­êi h­íng dÉn : PGS NguyÔn §øc NghÜa Bé m«n Khoa häc M¸y tÝnh , Khoa C«ng nghÖ Th«ng tin, §HBK Hµ Néi PhÇn I - S¾p xÕp kiÓu vun ®èng (Heapsort) 1.§èng : §èng lµ mét c©y nhÞ ph©n hoµn chØnh ®Æc biÖt mµ gi¸ trÞ l­u tr÷ t¹i mäi nót nh¸nh ®Òu lín h¬n hay b»ng gi¸ trÞ l­u trong hai nót con cña nã . 2. Vun ®èng S¾p xÕp kiÓu vun ®èng chia lµm hai giai ®o¹n : Mét d·y kho¸ k1,k2,…,kn biÓu diÔn cña mét c©y nhÞ ph©n hoµn chØnh mµ ki lµ gi¶ trÞ l­u trong nót thø i, nót con cña , nót con cña nót thø i lµ nót 2i vµ nót 2i+1, nót cha cña nót thø j lµ nót j div 2. §Çu tiªn c©y nhÞ ph©n biÓu diÔn b¶ng kho¸ ®­îc biÕn ®æi s¾p xÕp l¹i d·y kho¸ ®· cho ®Ó nã biÎu diÔn mét ®èng . Nh­ vËy kho¸ ë nót gèc cña ®èng chÝnh lµ kho¸ lín nhÊt (kho¸ tréi) so víi mäi kho¸ trªn c©y. Giai ®o¹n hai: lµ giai ®o¹n s¾p xÕp , nhiÒu l­ît xö lý ®­îc thùc hiÖn , mçi l­ît øng víi hai phÐp : - §­a kho¸ tréi vÒ vÞ trÝ thùc cña nã b»ng c¸ch ®æi chç cho kho¸ hiÖn ®ang ë vÞ trÝ ®ã - “Vun l¹i thµnh ®èng” ®èi víi c©y gåm c¸c kho¸ cßn l¹i (sau khi ®· lo¹i kho¸ tréi ra ngoµi). 3.Gi¶i thuËt: Mét nót l¸ cã thÓ ®­îc coi lµ mét c©y con ®· tho¶ m·n tÝnh chÊt cña ®èng råi .Nh­ vËy t¹o nªn t¹o ®èng hay vun ®èng cã thÓ tiÕn hµnh theo kiÓu tõ ®¸y lªn (botom-up) vµ bµi to¸n nµy sÏ ®­îc quy vÒ mét phÐp xö lý chung nh­ sau: chuyÓn ®æi thµnh ®èng cho mét c©y mµ con tr¸i vµ con ph¶i ®· lµ ®èng råi .Do ®ã ta cÇn x©y dung thñ tôc ADJUST nh»m thùc hiÖn c«ng viÖc nµy . §èi víi c©y nhÞ ph©n hoµn chØnh cã n nót th× nót øng víi chØ sè tõ [n/2] trë xuèng míi trë thµnh cha cña nót kh¸c nªn khi t¹o ®èng ADJUST chØ ¸p ®Æt víi nót vµo víi c¸c c©y mµ gèc mµ gèc cña nã øng víi chØ sè [n/2] , [n/2] -1, …, 1.Cßn v¬I vun ®èng th× l¹i ®¬n gi¶n h¬n . thñ tôc ADJUST lu«n lu«n ¸p ®Æt vµo c©y mµ gèc cña nã bao giê còng lµ nót ®Çu tiªn (øng víi chØ sè 1).V× vËy ta cÇn ®Õn hai thñ tôc : thñ tôc ADJUST vµ thñ tôc HEAPSORT . ADJUST coi nh­ mét ch­¬ng tr×nh con ®­îc gäi tíi trong HEAPSORT. Procedure ADJUST(i,n) {gi¶i thuËt to¸n nµy thùc hiÖn viÖc chØnh lý mét c©y nhÞ ph©n gèc i ®Ó nã tho¶ m·n ®­îc ®iÒu kiÖn cña ®èng .C©y con tr¸i vµ c©y con ph¶i cña i , nghÜa lµ c©y víi gèc 2i vµ 2i+1 , ®· tho¶ m·n ®iÒu kiÖn cña ®èng råi . Kh«ng cã nót nµo øng víi chØ sè lín h¬n n c¶} 1.{Khëi ®Çu } KEY := K[i] ; j := 2*i; 2.{Chän con øng víi kho¸ lín nhÊt trong hai con cña i } While j <= n do Begin If j<n and K[j] < K[j+1] then j := j+1 ; 3. {So s¸nh kho¸ cha víi kho¸ con lín nhÊt } If KEY < K[j] then Begin K[lj/2l] := KEY ; Return End;{Kho¸ cha lín h¬n } K[lj/2l] := K[j] ; j := 2*j ; {ChuyÓn k lªn trªn vµ ®i xuèng } End; 4. {§­a KEY vµo vÞ trÝ cña nã } K[lj/2l] := KEY; 5.return Procedure HEAPSORT(K ,n) {T¹o dèng ban ®Çu } for i := |n/2| down to 1 do call ADJUST(1,n) {S¾p xÕp } for i := n-1 down to 1 do Begin X := K[i] ; K[i] := K[i + 1] ; K[i+1] := X ; Call ADJUST(1,i) End 3.return phÇn ii – Mét sè øng dông 1.C¸c øng dông a) Bµi to¸n 1: X¸c ®Þnh xem cã bao nhiªu gi¸ trÞ kh¸c nhau trong m¶ng gåm n sè nguyªn d­¬ng . D÷ liÖu: File v¨n b¶n cã tªn DAYSO.TXT ghi n(n> 105 ) sè nguyªn . KÕt qu¶: §­a ra sè l­îng c¸c gi¸ trÞ kh¸c nhau trong file ®· cho vµ c¸c gi¸ trÞ t­¬ng øng theo thø tù gi¶m dÇn. b)Bµi to¸n 2: T×m k phÇn tö nhá nhÊt cña mét danh s¸ch gåm n phÇn tö : D÷ liÖu: File v¨n b¶n cã tªn THONGKE.TXT ghi d·y gåm n (n>106) sè thùc kh¸c nhau . KÕt qu¶: Víi mçi gi¸ trÞ k (k ≤ 1000 ) cÇn ®­a ra danh s¸ch k sè nhá nhÊt trong d·y sè cho trong file THONGKE.TXT theo thø tù gi¶m dÇn. NÕu cã mét c©y nhÞ ph©n hoµn chØnh ®Çy ®ñ , ta co thÓ dÔ dµng ®¸nh sè trªn c©y ®ã theo thø tù lÇn l­ît tõ møc 1 trë lªn , hÕt møc nµy sang møc kh¸c tõ tr¸i qua ph¶i ®èi víi c¸c nót ë mçi møc .Con cña nót thø i lµ c¸c nót thø 2i vµ 2i+1 hoÆc cha cña nót thø j lµ | j/2| . Víi viÖc yªu cÇu dïng ph­¬ng ph¸p s¾p xÕp nµy , b¶ng kho¸ sÏ cã cÊu tróc c©y nhÞ ph©n hoµn chØnh vµ l­u tr÷ kÕ tiÕp trong m¸y. Cµi ®Æt thuËt to¸n s¾p xÕp vun ®èng ®Ó ¸p dông trªn ch­¬ng tr×nh gi¶i hai bµi to¸n nãi trªn trªn m«i tr­êng Turbo C++ 6.0. V× vËy mµ nã ®ãng vai trß lµ mét thñ tôc ®­îc gäi trong c¸c ch­¬ng tr×nh gi¶i hai bµi to¸n . 2.Bµi to¸n 1: D÷ liÖu ®Çu vµo cña bµi to¸n lµ mét file v¨n b¶n ghi n sè nguyªn cã tªn DAYSO.TXT , do ®ã ta viÕt mét thñ tôc con Tao_file_so dïng thñ tôc rand() ®Ó nhËp c¸c sè nguyªn . Sau khi t¹o file v¨n b¶n chøa n sè nguyªn , tiÕp ®ã tiÕn hµnh ®äc file sau ®ã cµi ®Æt thñ tôc s¾p xÕp vun ®èng ®Ó s¾p xÕp vµ dïng thñ tôc chuyÓn .Nhê ®ã ta cã thÓ tiÕn hµnh so s¸nh c¸c sè vµ ®­a ra sè l­îng c¸c gi¸ trÞ kh¸c nhau , ®ång thêi khi sè l­îng thay ®æi th× còng ®­a ra gi¸ trÞ sè t­¬ng øng .Cuèi cïng , ®­a ra sè l­îng c¸c gi¸ trÞ kh¸c nhau vµ c¸c gi¸ trÞ ®ã tõ file DAYSO.TXT nãi trªn theo thø tù gi¶m dÇn. 3.Bµi to¸n 2: Víi bµi to¸n nµy , d÷ liÖu ®Çu vµo cã tªn lµ THONGKE.TXT còng lµ mét file v¨n b¶n gåm n phÇn tö sè thùc kh¸c nhau .T­¬ng tù víi bµi to¸n trªn, ta còng viÕt mét thñ tôc TAO_FILE_SO b»ng thñ tôc rand() . Nh­ng víi bµi to¸n nµy , ta ph¶i nhËp thªm gi¸ trÞ k (k<=1000) ®Ó nh»m ®­a ra k gi¸ trÞ nhá nhÊt theo thø tù gi¶m dÇn tõ file THONGKE.TXT nãi trªn. Thø tù thñ tôc Heapsort vµ thñ tôc Chuyen cã thay ®æi nh»m gi¶m thêi gian ch¹y ch­¬ng tr×nh khi kÝch th­íc file chøa sè lín. PhÇn Iii – Thùc nghiÖm Bµi to¸n 1 : Tr­íc khi s¾p xÕp : Ten file can tao la: DAYSO.TXT Day la so thu 1 : 41 Day la so thu 2 : 18467 Day la so thu 3 : 6334 Day la so thu 4 : 26500 Day la so thu 5 : 19169 Day la so thu 6 : 15724 Day la so thu 7 : 11478 Day la so thu 8 : 29358 Day la so thu 9 : 26962 Day la so thu 10 : 24464 So cac gia tri khac nhau la :10 Cac so khac nhau theo thu tu giam dan la: Gia tri a[10] : 29358 Gia tri a[9] : 26962 Gia tri a[8] : 26500 Gia tri a[7] : 24464 Gia tri a[6] : 19169 Gia tri a[5] : 18467 Gia tri a[4] : 15724 Gia tri a[3] : 11478 Gia tri a[2] : 6334 Gia tri a[1] : 41 Co muon chay lai chuong trinh nay khong ? An N hoac n de thoat Bµi to¸n 2: Ten file can tao la :THONGKE.TXT Hay doc so K 10 10 so nho nhat khac nhau theo thu tu giam dan la: Gia tri a[10] : 2995 Gia tri a[9] : 2082 Gia tri a[8] : 1869 Gia tri a[7] : 1842 Gia tri a[6] : 778 Gia tri a[5] : 491 Gia tri a[4] : 292 Gia tri a[3] : 288 Gia tri a[2] : 153 Gia tri a[1] : 41 Co muon chay lai chuong trinh nay khong? An Y hoac y de thoat PhÇn VI – Listing ch­¬ng tr×nh nguån ThuËt to¸n s¾p xÕp vun ®èng void adjust(long i, long n) { long j, key; key= b[i]; j=2*i; while (j<=n) { if ((j<n)&&(b[j]<b[j+1])) j=j+1; if (key >b[j]) { b[long(floor(j/2))] =key; break; } b[long(floor(j/2))]=b[j]; j=j*2; } b[long(floor(j/2))] = key; } //------------------------------------------------------- void Heap_sort() { long i,x; for(i=long(floor(n/2));i>=1;--i) adjust(i,n); for(i=n-1;i>=1;--i) { x=b[1];b[1]=b[i+1];b[i+1]=x; adjust(1,i); } 2.Bµi to¸n 1 #include #include #include #include const max=100, max1=3, max2=10; int a[max],b[max],d[max],n; enum boolean{F,T}; boolean c[max]; char filename[20]; void adjust(int i, int n); void Heap_sort(); void Tao_file_so(); void chuyen(); void Doc_file(); void main() { int i; char ch='y'; while ((ch!='n')&&(ch!='N')) {Tao_file_so(); Doc_file(); for(i=1;i<=max2;i++) cout<<"Day la so thu"<<i<<": "<<b[i]<<endl; chuyen(); Heap_sort(); cout<<" So cac gia tri khac nhau la: "<<n<<endl; cout<<"Cac so khac nhau theo thu tu giam dan la:"<<endl; for(i=n;i>=1;--i) cout<<"Gia tri a["<<i<<"] : "<<a[i]<<endl; cout<<" Co muon chay lai chuong trinh nay khong? An N hoac n de thoat"; cin>>ch; } } //-------------------------------------------------------- void Tao_file_so() { int i; double k; cout>filename; ofstream fout(filename); for(i=1;i<= max2;i++) { k=rand(); fout<<k<<endl; } fout.close(); } //-------------------------------------------------------- //------------------------------------------------------- void Doc_file() { int k,i; ifstream fin(filename); for(i=1;i<=max2;i++) { fin>>k; b[i]=k; } fin.close(); } //--------------------------------------------------------------------- void chuyen() { int i,j,k=1,m=0; for(i=1;i<=max2;i++) c[i]=T; for(i=1;i<=max2;i++) for(j=1;j<=max2;j++) { if((i!=j)&&(b[i]==b[j])&&c[i]) { c[j]= F; k=k+1;// Tan so lap cua tung so trong day } if ((j==max2)&&c[i]) { m=m+1;// so ca gia tri khac nhau a[m]=b[i]; d[m]=k; k=1; } } n=m; } //------------------------------------------------------- void Heap_sort() { int i,x; for(i=int(floor(n/2));i>=1;--i) adjust(i,n); for(i=n-1;i>=1;--i) { x=a[1];a[1]=a[i+1];a[i+1]=x; adjust(1,i); } } //---------------------------------------------------------- void adjust(int i, int n) { int j, key; key= a[i]; j=2*i; while (j<=n) { if ((j<n)&&(a[j]<a[j+1])) j=j+1; if (key >a[j]) { a[int(floor(j/2))] =key; break; } a[int(floor(j/2))]=a[j]; j=j*2; } a[int(floor(j/2))] = key; } 3.Bµi to¸n 2 #include #include #include #include const max=100, max2=100; int a[max],b[max],d[max]; long n; enum boolean{F,T}; boolean c[max]; char filename[20]; void adjust(long i, long n); void Heap_sort(); void Tao_file_so(); void chuyen(); void Doc_file(); void main() { long i,k; char ch='n'; while ((ch!='y')&&(ch!='Y')) { Tao_file_so(); Doc_file(); n=max2; Heap_sort(); chuyen(); cout>k; if (k<=n) { cout<<k<<" so nho nhat khac nhau theo thu tu giam dan la:"<<endl; for(i=k;i>=1;--i) cout<<"Gia tri a["<<i<<"] : "<<a[i]<<endl; } cout<<" Co muon chay lai chuong trinh nay khong? An Y hoac y de thoat "; cin>>ch; } } //-------------------------------------------------------- void Tao_file_so() { long i; int k; cout>filename; ofstream fout(filename); for(i=1;i<= max2;i++) { k=rand(); fout<<k<<" "; } fout.close(); } //-------------------------------------------------------- //------------------------------------------------------- void Doc_file() { long k,i; ifstream fin(filename); for(i=1;i<=max2;i++) { fin>>k; b[i]=k; } fin.close(); } //--------------------------------------------------------------------- void chuyen() { long i=1,j=2,k=1,m=0; while (j<=max2+1) { do { if ((b[i]==b[j])&&(j<=max2)) { j=j+1; k=k+1; }; }while ((b[j]==b[i])&&(j<=max2)); m=m+1; i=j; j=i+1; a[m]=b[i-1]; } n=m; } //------------------------------------------------------- void Heap_sort() { long i,x; for(i=long(floor(n/2));i>=1;--i) adjust(i,n); for(i=n-1;i>=1;--i) { x=b[1];b[1]=b[i+1];b[i+1]=x; adjust(1,i); } } //---------------------------------------------------------- void adjust(long i, long n) { long j, key; key= b[i]; j=2*i; while (j<=n) { if ((j<n)&&(b[j]<b[j+1])) j=j+1; if (key >b[j]) { b[long(floor(j/2))] =key; break; } b[long(floor(j/2))]=b[j]; j=j*2; } b[long(floor(j/2))] = key; } tµI liÖu tham kh¶o 1.§ç Xu©n L«i – CÊu tróc d÷ liÖu vµ gi¶i thuËt . NXB KHKT , 1997. 2.NguyÔn §øc NghÜa , NguyÔn T« Thµnh – To¸n rêi r¹c. NXB Gi¸o Dôc , 1997 môc lôc PhÇn I - S¾p xÕp kiÓu vun ®èng (Heapsort)……………………………….2 1.§èng ………………………………………………………………….2 2.Vun ®èng ……………………………………………………………..2 3.Gi¶i thuËt………………………………………………………………2 PhÇn II – Mét sè øng dông………………………………………………..4 1.C¸c øng dông ………………………………………………………....4 2. Bµi to¸n 1……………………………………………………………..4 3. Bµi to¸n 2……………………………………………………………..4 PhÇn III – Thùc nghiÖm …………………………………………………..6 PhÇn VI – Listing ch­¬ng tr×nh nguån……………………………………8 ThuËt to¸n s¾p xÕp vun ®èng ………………………………………..8 Ch­¬ng tr×nh gi¶i bµi to¸n 1………………………………………....8 Ch­¬ng tr×nh gi¶i bµi to¸n 2………………………………………..11 PhÇn V – Tµi liÖu tham kh¶o…………………………………………….15

Các file đính kèm theo tài liệu này:

  • docSắp xếp vung đống (Heapsort) và 1 số ứng dụng.DOC
Luận văn liên quan