HeapSort không những là một thuật toán sắp xếp hiệu quả mà còn xây dựng một cấu trúc dữ liệu quan trọng để biểu diễn hàng đợi có độ ưu tiên.

1. Đống (Heap)

Đống là một dạng cây nhị phân hoàn chỉnh đặc biệt mà giá trị lưu lại mọi nút có độ ưu tiên cao hơn hay bằng giá trị lưu trong hai nút con của nó.

2. Vun đống

Cho một dãy khoá k[1..n] là biểu diễn của một cây nhị phân hoàn chỉnh thì giá trị lưu trong nút thứ i, có hai nút con là 2i và 2i + 1. Để vun một nhánh cây gốc r thành đống, ta có thể coi hai nhánh con của nó là 2r và 2r+1 đã là đống rồi. Việc tự hiện vun đống sẽ xuất phát từ dưới lên. Gọi h là chiều cao của cây thì ta sẽ bắt đầu vun đống tại nút h / 2. Bởi vì những nút là ta coi như đã là đống với một phần tử. Ta cần xét bắt đầu từ phần tử đầu tiên có chứa nút lá để vun đống. Từ đó ta vun dần lên tới khi gặp nút gốc đầu tiên của đống.

Thuật toán HeapSort có hai thủ tục chính

  • Thủ tục heapify(root, endNode) vun cây gốc root thành đống trong điều kiện 2 * root và 2 * root + 1 đã là đống rồi. Các nút từ endNode + 1 tới n đã nằm ở vị trí đúng và không tính tới nữa
  • Thủ tục HeapSort mô tả lại quá trình vun đống và chón khoá theo ý tưởng trên.

Về độ phức tạp của thuật toán, cây nhị phân hoàn chỉnh có n nút thì chiều cao của nó là log(n) + 1. Trong trường hợp xấu nhất thủ tục heapify tìm đường đi từ nút gốc tới nút lá xa nhất bằng chiều cao của cây thì thời gian thực hiện một lần heapify là O(log(n)). Ta sẽ gọi n lần, vì vậy thời gian trong trường hợp xấu nhất của HeapSort cũng chỉ là O(nlog(n)). Việc đánh giá thời gian thực hiện trung bình phức tạp, ta chỉ thừa nhận là độ phức tạp của HeapSort là O(nlog(n))

Dưới đây là cách cài đặt thuật toán HeapSort bằng C++ bạn đọc có thể tham khảo

#include <iostream>

using namespace std;

void heapify(int root, int endNode);
void print();

int arr[5] = {1, 5, 4, 2, 3};
int n = 5;

int main() {
    int tmp;
    // vun cây từ dưới lên tạo thành đống
    for (int i = (n - 1) / 2; i >= 0; i --) {
        heapify(i, n);
    }
    for (int i = n - 1; i >= 0; i --) {
        // cho khoá lớn nhất về cuối dãy
        tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
        // vun đống lại từ vị trí root đầu tiên và không xét phần tử thứ >= i
        heapify(0, i);
    }
    print();
}

void heapify(int root, int endNode) {
    int child;
    int val = arr[root];
    // chừng nào chưa phải nút lá
    while (root * 2 + 1 < endNode) {
        child = (root * 2) + 1; // nút con trái
        // so sánh nút con trái và nút con phải nếu có
        if (child + 1 < endNode && arr[child] < arr[child + 1]) {
            child ++;
        }
        // nếu cả hai nút con nhỏ hơn root thì dừng
        if (arr[child] < val)
            break;
        // đặt giá trị của nút con lớn hơn vào nút gốc
        arr[root] = arr[child];
        root = child;
    }
    arr[root] = val;
}

void print() {
    for (int i = 0; i < n; i ++) {
        cout << arr[i] << '\t';
    }
    cout << endl;
}

Kết quả khi chạy chương trình trên sẽ như sau:

1	2	3	4	5