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

n
clean up, General fixes using AWB
n (clean up, replaced: ) → ) (2) using AWB)
n (clean up, General fixes 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ì 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]]
 
<source lang="c">
function heapSort(a[1..count], count) {
var int end := count
MakeHeap(a,count)
while end > 0
swap(a[end], a[1])
end := end - 1
DownHeap(a,0, end)
}
 
function MakeHeap(a, count) {
var int start := Int(count/2)
while start > 0
DownHeap(a, start, count)
start := start - 1
}
function DownHeap(a, start, count) {
var int i := start, j
j := i * 2
while j <= count {
if j+1 <= count and a[j] < a[j + 1]
j := j + 1
if a[i] < a[j]
swap(a[i], a[j])
i := j
j := j * 2
else
return
{{thuật toán sắp xếp}}
 
==Tham khảo==
{{tham khảo}}
[[Thể loại:Thuật toán sắp xếp|Vun đống]]
[[Thể loại:Đống (cấu trúc)]]