Chuyển tới nội dung chính

Heap sort (Sắp xếp vun đống)

Bạn sẽ học được gì

Heap sort kết hợp tốc độ O(n log n) của merge/quick với ưu điểm sắp tại chỗ O(1) bộ nhớ của các thuật toán cơ bản. Bí quyết: dùng cấu trúc max-heap (xem lại bài Heap ở Trụ 2) để liên tục rút ra phần tử lớn nhất và đặt nó về cuối mảng. Đổi lại, nó không ổn định.

1. Trực quan: cái máy luôn đưa phần tử lớn nhất lên đỉnh​

Một max-heap giống một cái cây kỳ diệu: dù bạn ném phần tử vào lộn xộn thế nào, phần tử lớn nhất luôn tự trồi lên gốc. Heap sort khai thác đúng điều đó:

  1. Vun (build) cả mảng thành một max-heap → phần tử lớn nhất nằm ở đỉnh.
  2. Đổi đỉnh (lớn nhất) với phần tử cuối → lớn nhất đã về đúng chỗ cuối cùng.
  3. Thu nhỏ heap đi 1, rồi vun lại (sift down) đỉnh mới → lại có lớn nhất ở đỉnh.
  4. Lặp lại cho tới khi heap chỉ còn 1 phần tử.
Max-heap luu trong mang (con cua i la 2i+1, 2i+2):

         9               mang: [9, 8, 6, 3, 5, 2]
       /   \
      8     6            doi 9 voi cuoi -> [2, 8, 6, 3, 5 | 9]
     / \   /             sift down 2    -> [8, 5, 6, 3, 2 | 9]
    3   5 2              ... lap lai, vung "da sap" lon dan ben phai

2. Ý tưởng cốt lõi: build heap + rút dần​

Thuộc tínhGiá trịGhi chú
Thời gianO(n log n)build O(n) + n lần rút, mỗi lần sift down O(log n)
Bộ nhớO(1)sắp tại chỗ ngay trên mảng, không cần mảng phụ
Ổn địnhKhôngphép đổi chỗ khi sift down phá vỡ thứ tự gốc

Khác biệt then chốt: heap sort cho O(n log n) đảm bảo (không như quick sort có thể tệ O(n^2)) mà vẫn O(1) bộ nhớ (không như merge sort tốn O(n)). Nghe có vẻ "ngon nhất", nhưng trên thực tế nó thường chậm hơn quick sort vì truy cập bộ nhớ nhảy lung tung (kém thân thiện với cache).

3. Chạy debug: sift down một phần tử​

sift_down là trái tim của heap sort: kéo một phần tử nhỏ "chìm" xuống cho tới khi nó lớn hơn cả hai con. Xem phần tử 2 ở đỉnh chìm xuống.

🐞 Sift down 2 trong heap [2, 8, 6, 3, 5]Bước 1/5
1heap = [2, 8, 6, 3, 5]   # dinh la 2, sai quy tac max-heap
2# con cua 0: trai=8 (vt1), phai=6 (vt2)
3# 8 lon nhat -> doi 2 voi 8
4# heap = [8, 2, 6, 3, 5]
5# con cua 1: trai=3 (vt3), phai=5 (vt4)
6# 5 lon hon 2 -> doi 2 voi 5
Biến tại bước này
heap[2, 8, 6, 3, 5]
👉 Đỉnh là 2 — vi phạm quy tắc max-heap.

4. Code chạy được​

Đang tải trình chạy code…

5. Phân tích: nhanh, gọn bộ nhớ, nhưng kém cache​

  • Vì sao O(n log n)? Bước build heap tốn O(n). Sau đó n lần rút, mỗi lần sift_down đi sâu tối đa log n tầng → O(n log n). Tổng vẫn O(n log n).
  • Bộ nhớ O(1): toàn bộ thao tác diễn ra ngay trên mảng — không mảng phụ. Đây là lợi thế lớn.
  • Đảm bảo trường hợp xấu: luôn O(n log n), không có "trường hợp xấu O(n^2)" như quick sort.
  • Vì sao thực tế hay thua quick sort? Heap nhảy qua các chỉ số 2i+1, 2i+2 → truy cập bộ nhớ rải rác, kém thân thiện với cache, nên hằng số ẩn lớn hơn.
  • Bẫy thường gặp: quên truyền kích thước n (hoặc end) khi sift down, khiến nó "vun" cả vùng đã sắp ở cuối — sai kết quả.

6. Mẫu nhận diện​

  • Cần O(n log n) đảm bảo mà vẫn O(1) bộ nhớ → heap sort là ứng viên sáng giá.
  • Bài toán cần liên tục lấy lớn nhất / nhỏ nhất (top-k, hàng đợi ưu tiên) → ý tưởng heap.
  • Hệ thống nhúng / bộ nhớ eo hẹp, không cho phép mảng phụ O(n) của merge sort → heap sort.
  • Nếu thấy "chọn ra k phần tử lớn nhất" → dùng heap kích thước k, không cần sắp cả mảng.

7. 🎮 Trò chơi: Hiểu heap sort​

🎮 Heap sort & max-heapCâu 1/4· Điểm 0· 🔥 0

Vun thành max-heap, rồi rút dần phần tử lớn nhất về cuối. O(n log n), tại chỗ, không ổn định.

Bộ nhớ phụ của heap sort là?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Độ phức tạp thời gian của heap sort trong mọi trường hợp là?
2. Heap sort có ổn định không?
3. Ưu thế lớn nhất của heap sort so với merge sort là?

9. Hoàn thành​

…

☑️ Tiếp theo: 3.1.5 — Ổn định & so sánh (tổng kết, bảng so sánh mọi thuật toán sắp xếp).