Các kỹ thuật sort — Heap Sort

Một mảng có thể "giả vờ" là một cây nhị phân hoàn chỉnh: phần tử tại chỉ số i có con trái tại 2i+1, con phải tại 2i+2. Heap Sort tận dụng đúng mẹo đó, không cần con trỏ hay bộ nhớ phụ nào.

Bài toán

Sắp xếp một mảng số nguyên tăng dần, đảm bảo O(n log n) xấu nhất và sắp xếp tại chỗ (không như Merge Sort cần O(n) bộ nhớ phụ).

Ý tưởng của Heap Sort

Bước 1 — Xây max-heap: biến mảng thành một max-heap (mọi nút cha ≥ hai nút con), bằng cách gọi heapify (sift-down) từ nút cha cuối cùng ngược lên gốc.

Bước 2 — Rút phần tử lớn nhất: gốc heap (a[0]) luôn là phần tử lớn nhất. Đổi chỗ nó với phần tử cuối mảng (đưa về đúng vị trí sắp xếp), thu nhỏ heap đi 1, rồi heapify lại gốc để khôi phục tính chất heap. Lặp lại cho đến khi heap chỉ còn 1 phần tử.

Độ phức tạp

So với Merge Sort, Heap Sort không cần bộ nhớ phụ nhưng không ổn định (không giữ thứ tự tương đối của các phần tử bằng nhau) và trong thực tế thường chậm hơn Quick Sort do truy cập bộ nhớ kém liên tục hơn (nhảy giữa các chỉ số 2i+1, 2i+2).

Ví dụ chạy tay

Mảng [6, 2, 9, 4] (0-indexed, cha của i là (i-1)/2):

1. Xây heap: heapify từ nút n/2 - 1 = 1 ngược về 0 → được max-heap [9, 4, 6, 2].
2. Đổi a[0]=9 với a[3]=2 → [2, 4, 6, 9], heapify phần [2, 4, 6] → [6, 4, 2, 9].
3. Đổi a[0]=6 với a[2]=2 → [2, 4, 6, 9], heapify phần [2, 4] → [4, 2, 6, 9].
4. Đổi a[0]=4 với a[1]=2 → [2, 4, 6, 9]. Kết quả cuối: [2, 4, 6, 9].

Ứng dụng / dạng bài hay gặp

• Cài đặt trực tiếp priority_queue — bản thân STL priority_queue của C++ chính là một binary heap cài trên mảng, giống hệt cấu trúc dùng trong Heap Sort.
• Bài toán "tìm k phần tử lớn nhất/nhỏ nhất" khi không muốn sắp xếp toàn bộ mảng: chỉ cần xây heap rồi rút ra k lần, O(n + k log n) thay vì O(n log n) sắp xếp toàn bộ.