D-ary heap, branching factor và bài toán top-K

Giới thiệu

Bài này mở heap 2 con thành nhiều con. Bạn tìm top K nhanh gọn.

Kiến thức cần nhớ

Heap nhiều nhánh là gì

• Nhánh là số con tối đa mỗi nút.
• Nhánh 3 thì con của i ở 3i+1 tới 3i+3.
• Nhánh to thì cây thấp hơn.
• Ví dụ đời thường: sếp quản 2 người và quản 4 người.

Nhánh to không phải luôn tốt

• Đẩy lên hưởng lợi vì cây thấp đi.
• Đẩy xuống mỗi tầng phải soi D con nên đắt.
• D quá to thì tiền soi nuốt tiền cây thấp.
• Lý thuyết cho thấy cân bằng tốt nhất giữa chèn và lấy gốc nằm ở $2 \le D \le 5$. Thực tế heap nhị phân hiếm khi nhanh nhất, D bằng 3 hoặc 4 thường thắng. Nên bắt đầu với D = 4 rồi đo trên dữ liệu thật.
• Ví dụ đời thường: họp 10 người lâu hơn họp 3.

Top-K bằng min-heap

• Giữ min-heap đúng K món.
• Món mới lớn hơn gốc thì thay gốc.
• Cuối cùng heap giữ K món lớn nhất.
• Ví dụ đời thường: giữ bảng top 3 điểm cao.
• Tốn bộ nhớ $O(K)$, khỏi xếp cả kho.

Ví dụ

• Input: dòng 5,1,4,2,3 với K=2. Output: heap giữ 4 và 5, gốc là 4.
• Giải thích: món nhỏ hơn gốc thì bỏ qua.

import heapq  # min-heap sẵn
h = []  # giữ đúng K món
for x in data:  # duyệt dòng dữ liệu
    heapq.heappush(h, x)  # thêm vào heap
    if len(h) > K:  # quá K thì bỏ nhỏ nhất
        heapq.heappop(h)

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-026/.

Bài 1: d-ary min-heap

template <class T, class Cmp = std::less<T>>
class DaryHeap {
 public:
  explicit DaryHeap(int d);   // d >= 2, sai thì ném invalid_argument
  void push(const T &x); T pop(); const T &top() const; size_t size() const;
};

Cha của i là (i - 1) / d. Con của i là d*i + 1 tới d*i + d.

d=3, push 5,1,4,2,3,9,0 -> pop hết ra 0,1,2,3,4,5,9
d=2 cho cùng kết quả với heap ngày 23
d=1                     -> ném invalid_argument

Bài 2: Tìm d tốt nhất

Chạy 2 kịch bản với $n = 10^6$ cho d = 2, 3, 4, 8, 16:

1. Nhiều push: push $n$ số ngẫu nhiên, pop $n/10$ lần.
2. Nhiều pop: push $n$ số, pop hết.

In bảng thời gian và số lần so sánh. Chỉ ra d tốt nhất cho mỗi kịch bản và giải thích bằng chiều cao cây $\log_d n$ và chi phí soi d con.

Bài 3: Top-K trên luồng dữ liệu (nâng cao)

stream 5,1,4,2,3, k=2           -> [5, 4]
stream có 3 số, k=5             -> trả đủ 3 số
"a b a c b a", k=2               -> ["a", "b"]

So thời gian topK với cách "đọc hết rồi std::sort" cho $n = 10^7$, $k = 100$.

✅ Tiêu chí hoàn thành

• Test mẫu pass với mọi d từ 2 tới 16.
• Bảng Bài 2 có số thật và kết luận d tốt nhất.
• topK chỉ dùng bộ nhớ $O(k)$, không lưu toàn bộ luồng.
• Giải thích được vì sao tìm top-K lớn nhất lại dùng min-heap.

❓ Câu hỏi ôn tập

• Nhánh của heap là gì?
• Vì sao nhánh to không luôn nhanh?
• Top-K dùng heap nào, cỡ bao nhiêu?
• Kể 3 ứng dụng lớn của heap?

🌕 Bạn đã hoàn thành ngày 26. Làm hết bài tập phía trên rồi sang ngày tiếp theo.