Định nghĩa: Một cây nhị phân nếu xét từ trên xuống dưới, từ trái sang phải mà khoá của một nút luôn ≥ nút con thì gọi là đống.
Cần lưu ý:
- Không nói gì, ngầm định là đống không tăng theo định nghĩa, còn trường hợp đống không giảm, đề sẽ nói rõ.
- Không nói gì, ngầm định là đống được lưu trữ vào dạng mảng danh sách. Lần lượt từ trái sang phải, hết mức nọ đến mức kia. Hết hàng nọ đến hàng kia.
Về chỉ số: Nếu i chỉ ra nút bất kì, tuy nhiên i ≤ n/2, thì :
- Con trái có chỉ số là: 2i
- Con phải có chỉ số là: 2i+1
- Khi nói con chung chung, ngầm định là con trái.

Một cây nhị phân, được gọi là đống cực đại nếu khóa của mọi nút không nhỏ hơn khóa các con của nó. Khi biểu diễn một mảng a[] bởi một cây nhị phân theo thứ tự tự nhiên điều đó nghĩa là a[i] ≥ a[2*i] và a[i] ≥ a[2*i +1] với mọi i =1..int(n/2). Ta cũng sẽ gọi mảng như vậy là đống. Như vậy trong đống a[1] (ứng với gốc của cây) là phần tử lớn nhất. Mảng bất kỳ chỉ có một phần tử luôn luôn là một đống.

Vun đống
Việc sắp xếp lại các phần tử của một mảng ban đầu sao cho nó trở thành đống được gọi là vun đống.

Vun đống tại đỉnh thứ i
Nếu hai cây con gốc 2 * i và 2 * i +1 đã là đống thì để cây con gốc i trở thành đống chỉ việc so sánh giá trị a[i] với giá trị lớn hơn trong hai giá trị a[2 * i] và a[2 * i + 1], nếu a[i] nhỏ hơn thì đổi chỗ chúng cho nhau. Nếu đổi chỗ cho a[2 * i], tiếp tục so sánh với con lớn hơn trong hai con của nó cho đến khi hoặc gặp đỉnh lá.


Vun một mảng thành đống

Để vun mảng a[1..n] thành đống ta vun từ dưới lên, bắt đầu từ phần tử a[j]với j =Int(n/2) ngược lên tới a[1]. (Thủ tục MakeHeap trong giả mã dưới đây).

Sắp xếp bằng vun đống
Đổi chỗ (Swap): Sau khi mảng a[1..n] đã là đống, lấy phần tử a[1] trên đỉnh của đống ra khỏi đống đặt vào vị trí cuối cùng n, và chuyển phần tử thứ cuối cùng a[n] lên đỉnh đống thì phần tử a[n] đã được đứng đúng vị trí.

Vun lại: Phần còn lại của mảng a[1..n-1] chỉ khác cấu trúc đống ở phần tử a[1]. Vun lại mảng này thành đống với n-1 phần tử.

Lặp: Tiếp tục với mảng a[1..n-1]. Quá trình dừng lại khi đống chỉ còn lại một phần tử.

---

Lưu ý khi đọc đề và làm bài:
- Khi đề bài ra như sau: Cho mảng X{X1, X2...Xn}, trong đó các giá trị X1, X2..Xn là các số cho sẵn.
- Hỏi: Chứng minh rằng đây không phải là đống, hoặc xác định xem X có phải là đống không. Thì khi làm chỉ cần chỉ ra 2 phần tử không thuộc tính chất của đống. Sau đó khẳng định luôn nó không phải là đống. Còn nếu khẳng định X là đống thì chứng minh theo tính chất của đống là với mọi chỉ số i <_i ≥ X_2i và X_i ≥ X_2i+1. Khi đề không yêu cầu viết chương trình giả mã, thì chỉ việc vẽ các bước để sắp xếp thành đống.

Ví dụ đề ra như sau:
Cho dãy X10 {12, 4, 8, 17,6, 5, 21, 33, 22, 20}
Hãy kiểm tra X có thoả mãn điều kiện là một đống không? Nếu không, hãy sắp xếp X sao cho là một đống.

Cách làm:
1. Kiểm tra X có thoả mãn điều kiện là một đống không?
Ta thấy với i = 1 thì X_i = X₁ = 12, X_2i = X₂ = 4, X_2i+1 = X₃ = 8 thoả mãn tính chất X_i ≥ X_2i và X_i ≥ X_2i

Với i = 2 thì X_i = X₂ = 4, X_2i = X₄ = 17, X_2i+1 = X₅ = 6 không thoả mãn tính chất X_i ≥ X_2i và X_i ≥ X_2i

Từ 2 trường hợp trên, kết luận X không phải là đống.

2. Sắp xếp X sao cho thành đống.
(Thực hiện vẽ đống theo từng công đoạn đổi chỗ Xi và các con của nó). Lưu ý Xi mà nhỏ hơn cả 2 con của nó, thì vẽ đổi chỗ cho con trái trước, sau đó mới đổi chỗ cho con phải. Vẽ theo thứ tự sau:
- Đổi chỗ ở nhánh bên phải nhất hàng cuối cùng → Đổi chỗ sang bên trái -→ hàng kế tương tự.

Thuật toán và giả mã:
Có nhiều sách viết, nhưng thống nhất theo cách viết thầy dạy, đừng có mà í ới theo các sách viết khác để nhầm lẫn là không có điểm đâu nha.

Thủ tục con vun đống:
Proc VĐ1(k: Chỉ số gốc, Temp: Giá trị chờ, m: chỉ số nút cuối cùng)
1. Stop = false;
2. While 2k < m & !Stop
a. j: = 2k
if ((j+1) ≤ m) & (Xj ≤ Xj+1) then j := j + 1;
b. if Xj > Temp then {Xk : = Xj ; k = j}
else Stop := true;
3. Xk: = Temp


Thủ tục tạo đống (sẽ gọi thủ tục vun đống nhiều lần đến khi đạt được mục đích thì thôi):
Proc Tạo đống;
n:=/X/
1. for i:= INT(n/2) downto 1 VĐ1(i, Xi, n)
2. For m := n - 1 downto 1
Temp := X_m+1;
VĐ1(1, Temp, m)
X_m+1 = Temp;
3. Output X


Anh Admin xem lại Tạo đống nhé, thuật toán này thày viết nhưng chưa đúng đâu
Em Son
Giải thuật của thầy còn thiếu (em đọc sách thầy Lôi em thấy thế), sách thầy Lôi dễ hiểu hơn nhiều.

các bạn các bác ơi!
tôi thấy môn CSDLGT chúng ta cần giải quyết triệt để hết các bài kiểm tra thầy tĩnh cho, để cho anh em học đuối như chung tôi nghiên cứu ko thì nguy mất. vì những bài đó khó, mà thầy ko chữa.
Muốn tham gia diễn đàn nhưng chỉ biết đọc thôi chứ chẳng biết gì khác để gửi trao đổi. Mhúc cả lớp thành công!

Mô phỏng thuật toán sắp xếp vun đống.

Admin: Phần này đã được Embed. Thanks. Đã nhấn thanks rồi, thanks thêm cái nữa nha. Màu nền này nghĩa là bài đã được đánh giá rất cao đó.

Bản quyền mô phỏng của Khoa học Máy tính
Computer Science
Faculty of Information Technology - Hanoi National University of Education

Nếu bạn không thấy mô phỏng hiện ra, nghĩa là máy bạn chưa cài java. Bạn phải thực hiện cài java vào máy bằng cách nhấn vào đường link sau: [You must be registered and logged in to see this link.]
Sau đó cứ việc nháy OK để java cài vào máy.

Tất cả các trang mô phỏng cơ sở, sẽ được viết theo dạng java cho nó nhẹ, nên bạn hãy cài java để xem nhé!

Hiện tại tôi có thể hướng dẫn các bạn mô phỏng bằng Flash nhưng không có thời gian nhiều. Chắc là nếu thi đỗ được, chúng ta sẽ làm lại toàn bộ mô phỏng dạng này bằng flash cho đẹp.

Đường link tham khảo các bài viết bằng sử dụng Flash căn bản (nếu không hiện tiếng Việt, xin chọn từ thựcđơn View, codepage ISO8859-1 (cái này tôi viết lâu rồi, từ hồi chưa chuẩn hoá unicode):
[You must be registered and logged in to see this link.]

Nháy tham khảo: [You must be registered and logged in to see this link.]
Giáo trình sử dụng: [You must be registered and logged in to see this link.]

Cảm ơn Admin đã quan tâm. Mình rất muốn post bài nhưng trình độ còn hạn chế nên chưa có nhiều bài để tham gia. Mình chỉ nhắc nhở các bạn khi làm bài CTDL phải có dòng Output kết quả vì theo đáp án nó chiếm 0.25 điểm đó.

Bình luận thủ tục con vun đống:
Thủ tục này nhằm biến các phần tử từ vị trí k đến vị trí n thành đống.
Các phần tử trước k và sau m không được thực hiện.
Proc VĐ1(k: Chỉ số gốc, Temp: Giá trị chờ, m: chỉ số nút cuối cùng)
1. Stop = false;// → Đặt một cờ nhằm làm chìa khoá để thoát khỏi vòng lặp bất cứ lúc nào
2. While 2k ≤ m & !Stop // → Chừng nào mà nút cha vẫn nằm trong khoảng cần xét và cờ cho phép thực hiện
a. j: = 2k // → Đặt biến j để thuận tiện truy cập nút con
if ((j+1) ≤ m) & (Xj << = Xj+1) then j:= j+1;
// → Nếu con phải lớn hơn con trái, thì chuyển sang con phải, đương nhiên không thoả mãn thì ngầm định con trái rồi.
b. if Xj > Temp then {Xk : = Xj ; k=j} // → Nếu con bằng với giá trị chờ, thì gán giá trị nút cha bằng giá trị của nút con
// → đồng thời chuyển xuống cấp thấp hơn, nút cha chính là nút con vừa xét
else Stop := true; // → Trường hợp nút con mà không lớn hơn nút cha
3. Xk: = Temp // → Gán nút cha hiện tại bằng giá trị chờ

Có điều gì đó có vẻ không ổn ở thủ tục này. Tại sao ở bước 2b lại không đổi chỗ giá trị nút cha Xk và nút con Xj nhỉ? Mà lại chỉ có gán giá trị của nút con cho nút cha. Có nghĩa là sau phép gán này, giá trị của nút con vẫn như cũ. Còn giá trị của nút cha bị đè bởi giá trị của nút con đưa vào. Giá trị này bị mất hoàn toàn, không thể khôi phục được vì mình có lưu nó vào chỗ nào đâu?

Ta có dám sửa lại thuật toán của thầy đưa ra cho chuẩn không?
Thôi thì cứ mạo muội xin phép thầy sửa lại cho nó tròn trịa. Bọn em không dám nói là cách của thày sai, mà chỉ dám phát biểu rằng cách của thầy còn thiếu một chút gì đó, có lẽ thầy quên không đưa vào. Ta đưa vào thế nào nhỉ?

Cảm giác như khi thầy viết dòng lệnh b. if Xj > Temp then {Xk : = Xj ; k=j} không phải là ý gán giá trị của nút con cho nút cha, mà là chuyển vị trí cần xét bắt đầu từ nút cha, sang vị trí cần xét bắt đầu từ nút con của nó. → Mà cũng cảm giác tiếp như là đống đã vun rồi ý. Thủ tục nếu là chuyển vị trí giống như tìm chỗ là một nút trong cây để đưa giá trị Temp vào. Thế nhưng nếu tìm chỗ để đưa giá trị temp vào thì giá trị trước khi đưa vào của nút đó phải để ở đâu?

Tôi thì cũng dốt về lập trình giả mã lắm, do quen viết bằng phần mềm thật rồi, nên cứ đưa tạm hướng giải quyết như thế này. Nếu các bạn thấy cần phải chỉnh chỗ nào thì ý kiến luôn để chúng ta có chương trình chuẩn. Tôi viết theo đúng kiểu của thầy:

Proc VĐ1(k: Chỉ số ban đầu, X: Dãy, m: chỉ số nút cần dừng lại)// Ở đây chỉ số m là chỉ số để chặn để không vun những giá trị có chỉ số sau m → nhằm sử dụng cho thuật toán sắp xếp.
1. Stop = false;// → Đặt một cờ nhằm làm chìa khoá để thoát khỏi vòng lặp bất cứ lúc nào (Giữ nguyên)
2. While 2k ≤ m & !Stop // → Chừng nào mà nút cha vẫn nằm trong khoảng cần xét và cờ cho phép thực hiện (Giữ nguyên)
a. j: = 2k // → Đặt biến j để thuận tiện truy cập nút con (Giữ nguyên)
if ((j+1) ≤ m) & (Xj << = Xj+1) then j:= j+1;
// → Nếu con phải lớn hơn con trái, thì chuyển sang con phải, đương nhiên không thoả mãn thì ngầm định con trái rồi. (Giữ nguyên)
b. if Xj > Xk then
                    Đổi (Xk : = Xj) ;
                    k=j // → Nếu con bằng với giá trị chờ, thì gán giá trị nút cha bằng giá trị của nút con
// → đồng thời chuyển xuống cấp thấp hơn, nút cha chính là nút con vừa xét
else Stop := true; // → Trường hợp nút con mà không lớn hơn nút cha
3. End.

Phải viết riêng thủ tục tạo đống:
Bất cứ một dãy nào, đều có thể dùng thủ tục này để tạo thành đống:

Proc Tạo Đống (X: Dãy, m: Chỉ số nút cần dừng lại)
1. i := Int(m/2)// Lấy vị trí bắt đầu vun là nút cha cuối cùng.
2.while i > 0 // Vun lùi dần len đến gốc
                    VĐ1( i, X, m);//Thực hiện thủ tục vun
                    i := i - 1;
End.

Bây giờ chúng ta sẽ viết lại thủ tục sắp xếp vun đống của thầy cho thật chuẩn:
Theo lời giảng của thầy là thầy cho giá trị gốc của đống xuống dưới cùng của dãy. Đưa giá trị mới vào đúng vị trí gốc. Nghĩa là, đống mới này sẽ được thêm 1 phần tử và mục đích là sẽ vun đống lại các phần tử từ đầu dãy đến phần tử cuối dãy cũ (chừa cái phần tử từ gốc đưa xuống ra). Ở vòng tiếp theo, mỗi vòng ta phải chừa thêm 1 phần tử. Vòng lặp thu hẹp đến khi hết các phần tử cần vun đống.

Proc Sắp xếp;
1. m:=/X/;
2. Tạo đống (X, m);
3. While m > 0 do
                    a. Đổi chỗ (X[m]; X[1]);// Đổi chỗ gốc và phần tử cuối.
                    b. m-- //Giảm bớt số phần tử đã đưa xuống
                    c. VĐ1(1, X, m); //Vun đống và chừa ra số các phần tử bị hạ xuống.
4. Output X.

Procedure VĐ1(i: byte; key: integer; m: byte);
{- sx trên mảng A[1...n]; key: giá trị khoá để so sánh; m: chỉ số của nút}
var: k,j: integer; Stop: boolean;
1) {gán k vào giá trị của Root}
a) stop:=false;
b) k: = i;
2) WHILE (2*k ≤ m) & !stop DO
          a) j := 2*k;
          b)IF (j < m) & ( X_j < X_j+1) THEN j := j + 1;
          c)IF key < X_j THEN X_k := X_j; k := j;
                    ELSE X_k := key;
3) End.

PROC Heap_Sort(n: byte);
var max, i, m: nteger;
1) FOR i: = n/2 DOWNTO 1 DO VĐ1(i, x_i, n);
2) FOR m := n - 1 DOWNTO 1 DO
          a) max: = X[1];
          b) VĐ1(1, max, m);
          c) m := max;
3) End.

Không biết khóa K23 học thế nào nhưng trong khóa K24 thì thuật toán của thày như sau (không biết có chép sai không? vì thày toàn viết từ giữa viết ra, mỗi đoạn lại viết một nơi [You must be registered and logged in to see this image.]
Proce. Heap (k: chỉ số ô trống; temp: giá trị; m:chỉ số chặn trên)
          FOR m:= n downto 2
          temp:= x_m ;
          x_m:= x₁;
          Heap(1; temp; m – 1;);
          WHILE (2k ≤ m) & !Stop
                    j:=2k;
                    if ((j + 1) ≤ m) & (x_j < x_j+1) THEN j:=j +1;
                    if (x_j > temp) { x_k := x_j ; k:=j;}
                    ELSE stop:=true;
          x_k := temp;
Output X;
Thuật toán trên khá giống thuật toán của Admin nhỉ? Chập 2 thành một mà. Nhưng đây mới chỉ là giải quyết bài toán cho mảng và sắp xếp thành một đống theo kiểu "giảm" nghĩa là có nút gốc lớn nhất, các nút cha lớn hơn hoặc bằng với nút con.
Tuy nhiên trong vở có chép (chính xác là "Vẽ" theo đúng lời của thày) thì sau khi thành 1 đống như trên. Còn có mấy hình vẽ cho kết quả cuối cùng là đống sắp xếp theo kiểu "tăng dần" nghĩa là có nút gốc nhỏ nhất, các nút cha nhỏ hơn nút con.
Thuật toán (phỏng đoán theo hình) là: đưa phần tử lớn nhất xuống lá cuối cùng, đưa nút con lên, tiếp tục".
Xin hỏi thuật toán như vậy viết thế nào ? liệu nó vẫn là thuật toán bên trên hay không?

Theo mình thì thuật toán của thầy vẫn là chuẩn. Bởi vì ngay từ đầu temp:=x(k)
bước b là chúng ta đi so sánh con trái và con phải với temp.