Lesson 09 — Heap Sort
3 module tương tác: (1) heap dạng cây + mảng song song, animate sift-down; (2) heap sort animator — build max-heap rồi extract-max về cuối; (3) build heap O(n) — vì sao tổng công tuyến tính dù cây cao log n.
1. Heap = cây + mảng song song — animate sift-down
Nhập mảng (số cách nhau bởi dấu phẩy), bấm Build heap để biến thành max-heap (sift-down từng node), hoặc sift-down gốc để xem một lần đẩy xuống. Cây và mảng được vẽ đồng bộ: cùng tô màu cùng lúc.
2. Heap sort animator — extract-max về cuối
Sau khi build max-heap, mỗi vòng: swap gốc (max) với cuối vùng heap → thu nhỏ heap → sift-down gốc. Phần xanh lá là vùng đã sắp xong (đông cứng). Quan sát: max lấp dần từ phải sang trái.
3. Build heap O(n) — vì sao tuyến tính?
Chọn số tầng của heap đầy. Cột cao = tổng công tầng đó (số node × chiều cao). Lá (k=0) đông node nhất nhưng sift 0 bước; gốc sift dài nhất nhưng chỉ 1 node. Tổng hội tụ về ~2n → O(n), KHÔNG phải O(n log n).