Thuật toán sắp xếp Heap Sort trong JavaScript

Heap Sort là một thuật toán sắp xếp dựa trên cấu trúc dữ liệu Heap (đống). Nó xây dựng một Heap tối đa (Max-Heap) từ mảng đầu vào, sau đó liên tục trích xuất phần tử lớn nhất từ Heap và đặt nó vào vị trí cuối cùng của mảng. Quá trình này tiếp tục cho đến khi toàn bộ mảng được sắp xếp.

Dưới đây là cách triển khai Heap Sort trong JavaScript:

function heapSort(arr) {
    let n = arr.length;

    // Xây dựng Max-Heap
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Trích xuất các phần tử từ Heap
    for (let i = n - 1; i >= 0; i--) {
        // Di chuyển root hiện tại đến cuối
        [arr[0], arr[i]] = [arr[i], arr[0]];

        // Gọi hàm heapify trên heap bị giảm
        heapify(arr, i, 0);
    }

    return arr;
}

// Hàm heapify một cây con với root tại chỉ số i
// n là kích thước của heap
function heapify(arr, n, i) {
    let largest = i; // Khởi tạo largest như root
    let left = 2 * i + 1; // chỉ số con trái = 2*i + 1
    let right = 2 * i + 2; // chỉ số con phải = 2*i + 2

    // Nếu con trái lớn hơn root
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // Nếu con phải lớn hơn largest hiện tại
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // Nếu largest không phải là root
    if (largest != i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]]; // Swap

        // Đệ quy heapify cây con bị ảnh hưởng
        heapify(arr, n, largest);
    }
}

// Ví dụ sử dụng:
let array = [12, 11, 13, 5, 6, 7];
console.log("Mảng ban đầu: " + array);
let sortedArray = heapSort(array);
console.log("Mảng sau khi sắp xếp: " + sortedArray);

Giải thích:

1. Hàm heapSort:

   • Tạo Max-Heap từ mảng đầu vào bằng cách gọi hàm heapify cho tất cả các nút không phải là lá bắt đầu từ giữa mảng.
   • Liên tục di chuyển phần tử lớn nhất (root của Heap) đến cuối mảng và giảm kích thước của Heap, sau đó gọi lại hàm heapify để điều chỉnh Heap.

2. Hàm heapify:

   • Khởi tạo largest như là root.
   • Tính toán chỉ số của các nút con trái và phải.
   • Nếu nút con trái lớn hơn root, đặt largest là con trái.
   • Nếu nút con phải lớn hơn largest hiện tại, đặt largest là con phải.
   • Nếu largest không phải là root, hoán đổi root với largest và đệ quy gọi lại hàm heapify cho cây con bị ảnh hưởng.

Thời gian và không gian:

• Thời gian:
  • O(n log n) trong mọi trường hợp (tốt nhất, trung bình và xấu nhất).
• Không gian:
  • O(1) vì Heap Sort là thuật toán sắp xếp tại chỗ, không yêu cầu thêm bộ nhớ ngoài mảng đầu vào.

Heap Sort là một thuật toán sắp xếp hiệu quả và ổn định với thời gian thực thi O(n log n) trong tất cả các trường hợp, tuy nhiên không ổn định vì không bảo toàn thứ tự của các phần tử bằng nhau.