Tổng quan
Heap Sort biến mảng thành một max-heap nhị phân, rồi liên tục lấy phần tử lớn nhất ra và đặt về cuối. Nó kết hợp đảm bảo O(n log n) của Merge Sort với tính tại chỗ của Quick Sort.
Heap Sort hoạt động thế nào?
- Xây một max-heap từ mảng sao cho phần tử lớn nhất nằm ở gốc.
- Hoán đổi gốc (giá trị lớn nhất) với phần tử cuối của heap.
- Thu nhỏ heap một phần tử và đẩy gốc mới xuống để khôi phục tính chất heap.
- Lặp lại đến khi heap rỗng; mảng lúc này đã sắp tăng dần.
Khi nào nên dùng?
- Khi cần O(n log n) xấu nhất mà không tốn bộ nhớ phụ như Merge Sort.
- Hệ thống eo hẹp bộ nhớ — nó sắp hoàn toàn tại chỗ.
- Cấu trúc heap này cũng là nền tảng cho hàng đợi ưu tiên.
Phân tích độ phức tạp
Xây heap tốn O(n), và mỗi trong n lần lấy ra tốn O(log n) để đẩy xuống, nên tổng thời gian là O(n log n) trong mọi trường hợp. Nó tại chỗ (O(1) bộ nhớ phụ) nhưng không ổn định, và thường chậm hơn Quick Sort trong thực tế do tính cục bộ bộ nhớ kém.
Câu hỏi thường gặp
Nếu Heap Sort là O(n log n) và tại chỗ, sao nó không phải mặc định?
Việc nhảy khắp mảng làm giảm hiệu năng cache CPU, nên Quick Sort thường nhanh hơn thực tế. Heap Sort tỏa sáng khi bắt buộc phải có đảm bảo O(n log n) xấu nhất.