Khác biệt giữa bản sửa đổi của “Sắp xếp vun đống”

* [[Tập tin:Tree array.PNG|nhỏ|230px|phải|Ví dụ về mảng và cây nhị phân tương ứng]]Mỗi mảng ''a''[1..n] có thể xem như một [[cây (lý thuyết đồ thị)|cây]] nhị phân gần đầy (có trọng số là các giá trị của mảng), với gốc ở phần tử thứ nhất, con bên trái của đỉnh ''a''[i] là ''a''[2*i] con bên phải là ''a''[2*i+1] (nếu mảng bắt đầu từ 1 còn nếu mảng bắt đầu từ 0 thì 2 con là ''a''[2*i+1] và ''a''[2*i+2]) (nếu 2*''i''<=''n'' hoặc 2*''i''+1<=''n'', khi đó các phần tử có chỉ số lớn hơn <math>int\left(\frac n 2 \right)</math> không có con, do đó là [[lá (lý thuyết đồ thị)|lá]]).

*[[Tập tin:Dong.PNG|nhỏ|230px|phải|Ví dụ mảng (45,23,35,13,15,12,15,7,9) là một đống]]

** 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 nhi 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.

** Một đống cực tiểu được định nghĩa theo các bất đẳng thức ngược lại: ''a''[i]<=''a''[2*i] và ''a''[i]<=''a''[2*i+1]. Phần tử đứng ở gốc cây cực tiểu là phần tử nhỏ nhất.

*Vun cây gốc '''a'''[2] ta được mảng '''a'''=(2,6,7,3,4,1,5)

*Vun cây gốc '''a'''[1] ta được mảng '''a'''=(7,6,5,3,4,1,2)

*Bây giờ '''a'''=(7,6,5,3,4,1,2) đã là đống.

 

/*6*/ Swap(a[0], a[1]);

}

 

void readList(recordtype a[])