Thao tác heap: BubbleUp, PushDown, Heapify, Top, Update
Mổ xẻ từng thao tác heap từ đẩy lên, đẩy xuống tới dựng heap tuyến tính, kèm phân tích số bước logarit.
Trung bìnhCấu trúc dữ liệu ~60 phút
Ôn lại trước khi học
Giới thiệu
Bài này mổ từng thao tác của heap. Bạn đẩy lên đẩy xuống đúng hướng.
Kiến thức cần nhớ
Đẩy lên và đẩy xuống
- Con vượt cha thì đổi chỗ rồi đi lên.
- Cha thua con thì đổi với con mạnh nhất rồi đi xuống.
- Mỗi vòng đi đúng 1 tầng nên tốn .
- Ví dụ đời thường: nhân viên giỏi thăng chức lên trên.
Chèn, lấy gốc, nhìn gốc
- Chèn: đặt vào đuôi mảng rồi đẩy lên.
- Lấy gốc: đưa đuôi lên gốc rồi đẩy xuống.
- Nhìn gốc chỉ tốn , không sửa gì.
- Ví dụ đời thường: lấy sếp ra rồi đôn người dưới lên.
Đổi ưu tiên và dựng nhanh
- Tăng ưu tiên thì đẩy lên, giảm thì đẩy xuống.
- Nhiều bài như Dijkstra chỉ cần giảm.
- Dựng từ n món sẵn thì duyệt ngược và đẩy xuống.
- Ví dụ đời thường: xếp lại tháp khi đổi điểm.
| Thao tác | Cách làm | Chi phí |
|---|---|---|
| Chèn | Đuôi rồi đẩy lên | |
| Lấy gốc | Đuôi thế gốc rồi đẩy xuống | |
| Nhìn gốc | Nhìn thôi | |
| Dựng sẵn | Đẩy xuống từ cuối về đầu |
Ví dụ
- Input: chèn 9 vào heap mà cha là 8. Output: đổi 1 lần rồi dừng.
- Giải thích: tổ tiên trên đã mạnh hơn nên khỏi đi tiếp.
💻 Bài tập
Ngôn ngữ: C++. Dùng tiếp Heap<T, Compare> ngày 23. Nộp vào day-024/.
Bài 1: Heapify và heap sort
| Hàm | Yêu cầu | Độ phức tạp |
|---|---|---|
void siftUp(std::vector<int>&, size_t i) | Đẩy lên | |
void siftDown(std::vector<int>&, size_t i, size_t n) | Đẩy xuống trong n phần tử đầu | |
void heapify(std::vector<int>&) | Duyệt từ n/2 - 1 về 0, gọi siftDown | |
void heapSort(std::vector<int>&) | Heapify rồi lần lượt đưa gốc về cuối |
heapify [3, 1, 6, 5, 2, 4] -> [6, 5, 4, 1, 2, 3]
heapSort [3, 1, 6, 5, 2, 4] -> [1, 2, 3, 4, 5, 6]
Đếm số lần đổi chỗ khi dựng heap bằng heapify so với push từng phần tử, với mảng tăng dần. Ghi kết quả.
Bài 2: Indexed heap có đổi ưu tiên
Viết IndexedMinHeap cho n phần tử có id 0..n-1:
| Hàm | Yêu cầu |
|---|---|
void push(int id, int key) | |
int popMin() | Trả id có key nhỏ nhất |
void decreaseKey(int id, int newKey) | newKey lớn hơn key cũ thì ném lỗi |
void update(int id, int newKey) | Tăng hoặc giảm, tự chọn siftUp hay siftDown |
bool contains(int id) |
Giữ mảng pos[id] để biết id đang ở đâu trong heap. Mọi thao tác .
push (0,50) (1,20) (2,30)
decreaseKey(0, 10) -> popMin = 0
update(1, 40) -> popMin = 2, rồi 1
Bài 3: Gộp K danh sách đã xếp (nâng cao)
Cho K vector đã xếp tăng dần. Gộp thành 1 vector xếp tăng dần trong , với N là tổng số phần tử.
[[1,4,7], [2,5,8], [0,9]] -> [0,1,2,4,5,7,8,9]
[[], [1], []] -> [1]
Ứng dụng: sinh 8 file, mỗi file 10^5 số đã xếp. Gộp thành 1 file mà không đọc toàn bộ vào RAM cùng lúc (đọc từng số một).
✅ Tiêu chí hoàn thành
- Test mẫu pass.
heapSortpass test ngẫu nhiên so vớistd::sort. -
IndexedMinHeapgiữposđúng sau mọi thao tác (viết hàm kiểm tra). - Có số liệu chứng minh
heapifyrẻ hơnpushtừng phần tử. - Bài 3 gộp file đúng, bộ nhớ chỉ .
❓ Câu hỏi ôn tập
- Đẩy lên dùng khi nào?
- Đẩy xuống dùng khi nào?
- Lấy gốc vì sao đưa đuôi lên?
- Dựng sẵn nhanh hơn chèn lẻ ở đâu?
🌕 Bạn đã hoàn thành ngày 24. Làm hết bài tập phía trên rồi sang ngày tiếp theo.