Thuật toán Heap Sort (Sắp xếp vun đống)

Heap Sort thực hiện trên cấu trúc dữ liệu Heap (cây nhị phân hoàn chỉnh). Có hai loại: Min-heap (gốc nhỏ nhất) và Max-heap (gốc lớn nhất). Sau khi xây heap, xóa phần tử gốc, đưa phần tử cuối lên gốc, rồi heapify lại. Lặp lại cho đến khi mảng được sắp xếp.

Độ phức tạp Heap Sort

• Time Complexity: O(n log n)
• Space Complexity: O(1)

Input và Output

Input: Danh sách chưa sắp xếp: 30 8 99 11 24 39
Output: Mảng trước sắp xếp: 30 8 99 11 24 39
Mảng sau sắp xếp: 8 11 24 30 39 99

Thuật toán

heapify(array, size)

Begin
  for i := 1 to size do
    node := i
    par := floor(node / 2)
    while par >= 1 do
      if array[par] < array[node] then
        swap array[par] with array[node]
      node := par
      par := floor(node / 2)
    done
  done
End

heapSort(array, size)

Begin
  for i := n down to 1 do
    heapify(array, i)
    swap array[1] with array[i]
  done
End

Ví dụ (C++)

#include <iostream>
using namespace std;

void display(int *array, int size) {
    for(int i = 1; i <= size; i++) cout << array[i] << " ";
    cout << endl;
}

void heapify(int *array, int n) {
    for(int i = 1; i <= n; i++) {
        int node = i, par = node / 2;
        while(par >= 1) {
            if(array[par] < array[node]) swap(array[par], array[node]);
            node = par;
            par = node / 2;
        }
    }
}

void heapSort(int *array, int n) {
    for(int i = n; i >= 1; i--) {
        heapify(array, i);
        swap(array[1], array[i]);
    }
}

int main() {
    int n; cout << "Nhập số phần tử: "; cin >> n;
    int arr[n+1]; // index từ 1
    cout << "Nhập phần tử:" << endl;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    cout << "Trước sắp xếp: "; display(arr, n);
    heapSort(arr, n);
    cout << "Sau sắp xếp: "; display(arr, n);
}

Kết quả

Nhập số phần tử: 6
Nhập phần tử: 30 8 99 11 24 39
Trước sắp xếp: 30 8 99 11 24 39
Sau sắp xếp: 8 11 24 30 39 99

Đặc điểm: Heap Sort in-place, không ổn định (unstable), O(n log n) mọi trường hợp. Dùng Max-heap để sắp xếp tăng dần. Thường dùng khi cần đảm bảo hiệu năng worst-case và bộ nhớ hạn chế.