đề 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> 10
5
) 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>10
6
) 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
CNTT-
KS17
1
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ị lu trữ tại mọi nút nhánh đều

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.

CNTT-
KS17
2
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 }

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>10
6
) 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à lu 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:
CNTT-
KS17
4
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

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
2. 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
CNTT-
KS17
6