Sắp xếp vun đống
Bách khoa toàn thư mở Wikipedia
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.
Mục lục |
[sửa] Đống (Heap)
-
Mỗi mảng a[1..n] có thể xem như một 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 2 * i < = n hoặc 2 * i + 1 < = n, khi đó các phần tử có chỉ số lớn hơn
Ví dụ về mảng và cây nhị phân tương ứng
không có con, do đó là lá). -
Ví dụ mảng (43,23,35,13,15,12,15,7,9) là một đống
Mảng, hay cây nhị phân, được gọi là đống nếu mỗi phần tử của nó đều không nhỏ hơn các con của nó, nghĩa là a[i] > = a[2 * i] và a[i] > = a[2 * i + 1] với mọi i = 1..int(n / 2). Như vậy trong đống a[1] 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.
[sửa] Vun đống
Việc sắp xếp lại các phần tử của một mảng ban đầu sao cho nó trở thành đống được gọi là vun đống.
[sửa] Vun đống tại đỉnh thứ i
Nếu hai cây con gốc 2 * i và 2 * i + 1 đã là đống thì để cây con gốc i trở thành đống chỉ việc so sánh giá trị a[i] với giá trị lớn hơn trong hai giá trị a[2 * i] và a[2 * i + 1], nếu a[i] nhỏ hơn thì đổi chỗ chúng cho nhau. Nếu đổi chỗ cho a[2 * i], tiếp tục so sánh với con lớn hơn trong hai con của nó cho đên khi hoặc gặp đỉnh lá. (Thủ tục DownHeap trong giả mã dưới đây)
[sửa] Vun một mảng thành đống
Để vun cả mảng a[1..n] thành đống ta vun từ dưới lên, bắt đầu từ phần tử a[j] = Int(n / 2) ngược lên tới a[1]. (Thủ tục MakeHeap trong giả mã dưới đây)
[sửa] Sắp xếp bằng vun đống
- Đổi chỗ (Swap): Sau khi mảng a[1..n] đã là đống, lấy phần tử a[1] trên đỉnh của đống ra khỏi đống đặt vào vị trí cuối cùng n, và chuyển phẩn tử thứ cuối cùng a[n] lên đầu đống thì phần tử a[n] đã được sắp. Phần còn lại của mảng a[1..n − 1] chỉ khác cấu trúc đống ở phần tử a[1]. Vun lại mảng này thành đống với n-1 phần tử. Quá trình dừng lại khi đống chỉ còn lại một phần tử.
[sửa] Ví dụ
Cho mảng a=(2,3,5,6,4,1,7)
- Ở đây n = 7. Các phần tử từ a[4] đến a[7] là lá.
[sửa] Vun đống
- Vun cây gốc a[3] ta được mảng a=(2,3,7,6,4,1,5)
- 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,2,3,4,1,5)
- Bây giờ a=(7,6,2,3,4,1,5) đã là đống.
[sửa] Sắp xếp
- Đổi chỗ a[1] với a[7]: a=(5,6,2,3,4,1,7)
- và vun lại mảng a[1..6] ta được mảng a=(6,5,2,3,4,1,7)
- Đổi chỗ a[1] với a[6]: a=(1,5,2,3,4,6,7)
- và vun lại mảng a[1..6] ta được mảng a=(5,4,2,3,1,6,7)
- Đổi chỗ a[1] với a[6]: a=(1,5,2,3,4,6,7)
- và vun lại mảng a[1..5] ta được mảng a=(5,4,2,3,1,6,7)
- Đổi chỗ a[1] với a[5]: a=(1,4,2,3,5,6,7)
- và vun lại mảng a[1..4] ta được mảng a=(4,3,2,1,5,6,7)
- Đổi chỗ a[1] với a[4]: a=(1,3,2,4,5,6,7)
- và vun lại mảng a[1..3] ta được mảng a=(3,1,2,4,5,6,7)
- Đổi chỗ a[1] với a[3]: a=(2,1,3,4,5,6,7)
- và vun lại mảng a[1..2] ta được mảng a=(2,1,3,4,5,6,7)
- Đổi chỗ a[1] với a[2]:a=(1,2,3,4,5,6,7)
- Mảng còn lại chỉ một phần tử. Quá trình sắp xếp đã xong.
[sửa] Giả mã
function heapSort(a[1..count], count) {
var int end := count
MakeHeap(a,count)
while end > 0
swap(a[end], a[1])
DownHeap(a, 1, end)
end := end - 1
}
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
while i * 2 <= count {
j := i * 2
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
else
return
}
}
