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

n
→‎Đống (Heap): replaced: 2 con → hai con using AWB
n (→‎Đống (Heap): replaced: 2 con → hai con using AWB)
 
==Đống (Heap)==
* [[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ì 2hai 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.