Thuật toán HeapSort

Có tên tiếng Việt là Sắp xếp vun đống

1. Ý tưởng

1.1. Đống

  • 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 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 int\left( \frac n 2 \right ) không có con, do đó là ).
  • 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.
    • Một đống cực tiểu được định nghĩa theo các bất đẳng thức ngược lại: a[i]<=a[2*i] và a[i]<=a[2*i+1]. Phần tử đứng ở gốc cây cực tiểu là phần tử nhỏ nhất.

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

1.2.1. Vun đống thứ i

Nếu hai cây con gốc 2 * i2 * 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]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)

1.2.2. Vun một mảng thành đống

Để vun mảng a[1..n] thành đống ta vun từ dưới lên, bắt đầu từ phần tử a[j]với j =Int(n/2) ngược lên tới a[1]. (Thủ tục MakeHeap trong giả mã dưới đây) kho qua

1.2.3. 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 đỉnh đống thì phần tử a[n] đã được đứng đúng vị trí.
Vun lại: 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ử.
Lặp: Tiếp tục với mảng a[1..n-1]. Quá trình dừng lại khi đống chỉ còn lại một phần tử.
2. giả mã

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, 1, 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

     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
     }
 }
3. Cài đặt chương trình