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

®Ò 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