Thuật toán Heap Sort là gì? Giải thích dễ hiểu kèm demo trực quan

Thuật toán Heap Sort là gì? Giải thích dễ hiểu kèm demo trực quan

Heap Sort là một thuật toán sắp xếp mạnh mẽ dựa trên cấu trúc dữ liệu Heap, thường là Max-Heap khi sắp xếp tăng dần. Thuật toán này có độ phức tạp thời gian O(n log n) ổn định, không phụ thuộc vào việc mảng ban đầu có sắp xếp hay chưa.

Khác với Quick Sort có thể rơi vào trường hợp tệ nhất O(n²), Heap Sort luôn đảm bảo hiệu năng ổn định nhờ đặc tính của Heap.

Heap Sort giải bài toán gì?

• Sắp xếp mảng theo thứ tự tăng dần hoặc giảm dần.
• Dùng khi cần thuật toán ổn định, có hiệu năng dự đoán được.

Ý tưởng chính của Heap Sort

Heap Sort hoạt động theo hai giai đoạn:

1. Dựng Max-Heap: phần tử lớn nhất nằm ở root (vị trí 0).
2. Sort:
   • Đổi chỗ root với phần tử cuối.
   • Giảm kích thước heap.
   • Gọi heapify để đưa root về đúng vị trí.

Ví dụ minh họa

[5, 3, 8, 4, 2, 7]

Quá trình:

• Dựng Max-Heap → [8, 5, 7, 4, 2, 3]
• Swap 8 với 3 → heapify → …
• Lặp lại cho đến khi mảng được sắp xếp hoàn toàn.

Demo Heap Sort bằng JavaScript

Demo thể hiện:

• Xây heap từng bước (heapify từ dưới lên).
• Highlight phần tử đang được so sánh.
• Highlight phần tử đang được swap.
• Thu nhỏ heap sau mỗi lần đưa max ra cuối.

Phân tích code

1. Ghi lại toàn bộ bước build-heap & heapify

function heapSortWithSteps(arr) {
    var a = arr.slice();
    var steps = [];

    function swap(i, j) {
        var t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    function heapify(n, i) {
        var largest = i;
        var left = 2 * i + 1;
        var right = 2 * i + 2;

        if (left < n) {
            steps.push({
                type: "compare",
                i: largest,
                j: left,
                array: a.slice()
            });
            if (a[left] > a[largest]) {
                largest = left;
            }
        }

        if (right < n) {
            steps.push({
                type: "compare",
                i: largest,
                j: right,
                array: a.slice()
            });
            if (a[right] > a[largest]) {
                largest = right;
            }
        }

        if (largest !== i) {
            swap(i, largest);
            steps.push({
                type: "swap",
                i: i,
                j: largest,
                array: a.slice()
            });

            heapify(n, largest);
        }
    }

    var n = a.length;

    steps.push({ type: "build_start", array: a.slice() });

    for (var i = Math.floor(n / 2) - 1; i >= 0; i--) {
        steps.push({
            type: "heapify_node",
            index: i,
            array: a.slice()
        });
        heapify(n, i);
    }

    steps.push({ type: "build_done", array: a.slice() });

    for (var i = n - 1; i > 0; i--) {
        swap(0, i);
        steps.push({
            type: "swap_root",
            to: i,
            array: a.slice()
        });

        heapify(i, 0);
    }

    return { steps: steps, sorted: a };
}

2. Hiển thị mảng + highlight

function renderHeapArray(container, arr, opts) {
    opts = opts || {};
    var active = opts.active;
    var active2 = opts.active2;
    var heapSize = opts.heapSize;

    container.innerHTML = "";
    arr.forEach(function(value, index) {
        var div = document.createElement("div");
        div.className = "heap-cell";

        if (heapSize != null && index >= heapSize) {
            div.classList.add("heap-out");
        }

        if (index === active) {
            div.classList.add("heap-active");
        }
        if (index === active2) {
            div.classList.add("heap-active2");
        }

        div.textContent = value;
        container.appendChild(div);
    });
}

3. Animation từng bước

function playHeapSteps(steps, sortedArray) {
    var index = 0;
    heapLog.innerHTML = "";
    heapResult.textContent = "Đang chạy thuật toán...";

    function next() {
        if (index >= steps.length) {
            renderHeapArray(heapArray, sortedArray, { heapSize: sortedArray.length });
            heapResult.innerHTML =
                "Mảng đã được sắp xếp: <strong>[" + sortedArray.join(", ") + "]</strong>";
            return;
        }

        var step = steps[index];
        var msg = "";
        var opts = {};

        if (step.type === "build_start") {
            msg = "Bắt đầu dựng Max-Heap.";
        } else if (step.type === "heapify_node") {
            msg = "Heapify node tại vị trí " + step.index + ".";
        } else if (step.type === "compare") {
            msg =
                "So sánh phần tử tại " +
                step.i +
                " và " +
                step.j +
                ".";
            opts.active = step.i;
            opts.active2 = step.j;
        } else if (step.type === "swap") {
            msg =
                "Đổi chỗ phần tử tại vị trí " +
                step.i +
                " và " +
                step.j +
                " để duy trì Max-Heap.";
            opts.active = step.i;
            opts.active2 = step.j;
        } else if (step.type === "build_done") {
            msg = "Đã dựng xong Max-Heap.";
        } else if (step.type === "swap_root") {
            msg =
                "Đưa phần tử lớn nhất (root) về cuối heap (vị trí " +
                step.to +
                ").";
            opts.heapSize = step.to;
        }

        renderHeapArray(heapArray, step.array, opts);

        var p = document.createElement("p");
        p.innerHTML = msg;
        heapLog.appendChild(p);
        heapLog.scrollTop = heapLog.scrollHeight;

        index++;
        setTimeout(next, 650);
    }

    next();
}

Khi nào nên dùng Heap Sort?

• Dữ liệu rất lớn và cần hiệu năng ổn định.
• Khi muốn tránh worst-case của Quick Sort.
• Khi cần sắp xếp tại chỗ (in-place) với O(1) memory.

Kết luận

Heap Sort là một thuật toán mạnh mẽ với hiệu năng ổn định O(n log n).
Demo trực quan cho thấy cách dựng heap, swap root và heapify từng bước — giúp bạn dễ dàng hiểu cơ chế hoạt động phía sau.