Để thực hiện sắp xếp đống hiệu quả, việc xây dựng cấu trúc đống từ mảng ban đầu là bước then chốt — không chỉ ảnh hưởng đến độ phức tạp thời gian mà còn quyết định tính ổn định và khả năng mở rộng của thuật toán.

I. Chuyển đổi mảng thành đống — hai chiến lược nền tảng

Một mảng chưa được sắp xếp có thể được biến đổi thành đống theo hai hướng tiếp cận chính:

• Chiến lược "chèn từng phần tử": Duyệt từ chỉ số 1 đến cuối mảng, gọi hàm điều chỉnh lên (adjustUp) cho mỗi vị trí. Cách này mô phỏng thao tác chèn liên tục vào đống rỗng, nhưng dẫn đến chi phí tổng thể cao hơn do mỗi lần điều chỉnh có thể mất O(log n).
• Chiến lược "xây đáy-lên": Bắt đầu từ nút cha của nút lá cuối cùng — tức là tại chỉ số (n - 2) / 2 — và lặp ngược về đầu mảng, áp dụng hàm điều chỉnh xuống (adjustDown). Đây là phương pháp tối ưu, tận dụng đặc tính cấu trúc cây đầy đủ để đạt độ phức tạp xây dựng đống chỉ O(n).

II. Sắp xếp tăng dần bằng đống lớn (max-heap)

Để thu được dãy kết quả tăng dần, ta sử dụng đống lớn vì:

• Phần tử lớn nhất luôn nằm ở gốc (a[0]), nên dễ dàng đưa nó về vị trí cuối cùng đã "đóng băng".
• Sau mỗi lần hoán đổi giữa gốc và phần tử cuối chưa được sắp, ta giảm kích thước vùng làm việc và điều chỉnh lại phần còn lại thành đống lớn.

Ví dụ minh họa với mảng đầu vào:

int arr[] = {4, 6, 2, 1, 5, 8, 2, 9};
int size = sizeof(arr) / sizeof(int);
heapSortAscending(arr, size); // Kết quả: 1 2 2 4 5 6 8 9

III. So sánh độ phức tạp thời gian

IV. Triển khai đầy đủ với tối ưu hóa xây đống

Dưới đây là phiên bản cải tiến, loại bỏ vòng lặp xây đống không cần thiết và sử dụng kỹ thuật "bottom-up heapify":

void heapSortAscending(int* nums, int n) {
    // Bước 1: Xây đống lớn từ mảng — bắt đầu từ nút cha cuối cùng
    for (int i = (n - 2) / 2; i >= 0; --i) {
        siftDown(nums, n, i);
    }

    // Bước 2: Lặp để trích xuất phần tử lớn nhất
    for (int end = n - 1; end > 0; --end) {
        swap(&nums[0], &nums[end]);     // Đưa phần tử lớn nhất về cuối
        siftDown(nums, end, 0);           // Điều chỉnh lại vùng [0..end-1]
    }
}

// Hàm trợ giúp: điều chỉnh xuống từ vị trí root trong phạm vi size
void siftDown(int* arr, int size, int root) {
    while (true) {
        int largest = root;
        int left = 2 * root + 1;
        int right = 2 * root + 2;

        if (left < size && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < size && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest == root) break;

        swap(&arr[root], &arr[largest]);
        root = largest;
    }
}

V. Ghi chú về sắp xếp giảm dần

Để thu được thứ tự giảm dần, chỉ cần xây dựng đống nhỏ (min-heap) thay vì đống lớn, sau đó thực hiện tương tự: hoán đổi gốc với phần tử cuối và điều chỉnh lại. Tuy nhiên, trong hầu hết các trường hợp thực tế, việc đảo ngược kết quả tăng dần thường đơn giản và an toàn hơn.