682.729
lần sửa đổi
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(
* [[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
MakeHeap(a,count)
while end > 0
swap(a[end], a[1])
end
DownHeap(a,0, end)
}
function MakeHeap(a, count) {
var int start
while start > 0
DownHeap(a, start, count)
start
}
function DownHeap(a, start, count) {
var int i
j
while j <= count {
if j+1 <= count and a[j] < a[j + 1]
j
if a[i] < a[j]
swap(a[i], a[j])
i
j
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)]]
|