Động lực

Heap Sort sử dụng một đống nhị phân để liên tục tìm phần tử lớn nhất còn lại trong thời gian O(log n), nhờ đó sắp xếp ổn định với độ phức tạp O(n log n).

Tại sao nên học Heap Sort?

• Đảm bảo O(n log n): không giống Quick Sort, thuật toán này không có trường hợp xấu nhất O(n²).
• Sắp xếp tại chỗ: thuật toán sắp xếp ngay trong mảng ban đầu và chỉ cần thêm O(1) bộ nhớ, không giống Merge Sort.
• Trực quan về đống: thuật toán giúp củng cố cách lưu trữ đống trong mảng và cách thao tác sift-down duy trì tính hợp lệ của đống.

Nếu bạn đã học khóa học Heap trong loạt bài này, Heap Sort chính là cấu trúc dữ liệu đó được áp dụng làm thuật toán sắp xếp.