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

'''Sắp xếp vun đống''' (''Heapsort'') dựa trên một [[cấu trúc dữ liệu]] được gọi là [[đống nhị phân]] (''binary heap''), gọi đơn giản là đống. Trong mục này chỉ nói về đống trong bài toán sắp xếp.

 

==Đố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ì 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á]]).

 

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