Khi xử lý các luồng dữ liệu thời gian thực (Real-time Streaming) trong hệ thống tài chính, tại sao việc sử dụng Max-Heap lại là lựa chọn tiêu chuẩn để tính toán giá trị trung bình trượt (Moving Median) và nhược điểm của cách tiếp cận này là gì?

Question

Accepted Answer

Trong các bài toán xử lý luồng dữ liệu thời gian thực yêu cầu tính toán liên tục giá trị trung bình (Moving Median) hoặc phân vị (Percentile), cấu trúc dữ liệu được áp dụng tiêu chuẩn là sự kết hợp giữa một Max-Heap và một Min-Heap thay vì chỉ dùng một Heap đơn lẻ.
Cơ chế hoạt động

Max-Heap lưu trữ nửa nhỏ hơn của tập hợp dữ liệu.
Min-Heap lưu trữ nửa lớn hơn của tập hợp dữ liệu.
Phần tử gốc của hai Heap này sẽ đại diện cho các giá trị ở giữa, giúp việc tính toán Median đạt độ phức tạp O(1) sau khi cân bằng xong kích thước hai Heap.

Tại sao dùng cặp Heap này tối ưu hơn mảng hoặc danh sách?

Nếu sử dụng mảng hoặc danh sách đã sắp xếp, mỗi khi có dữ liệu mới đổ vào (streaming), thao tác chèn sẽ mất độ phức tạp O(N) do phải dịch chuyển phần tử.
Sử dụng cấu trúc 2 Heap giúp thao tác chèn và cân bằng lại dữ liệu chỉ mất O(log N), đáp ứng tốt yêu cầu độ trễ thấp (low latency) của hệ thống tài chính.

Nhược điểm và thách thức thực chiến

Việc loại bỏ một phần tử bất kỳ (không nằm ở gốc) khỏi Heap có độ phức tạp O(N) trừ khi áp dụng kỹ thuật đánh dấu lười (Lazy Deletion) kết hợp với HashMap để theo dõi các phần tử cần xóa khỏi cửa sổ trượt (Sliding Window).

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi heaps and maps liên quan cùng chủ đề