You are building a service that must return the top K highest-scoring items out of N items (N K), and the request arrives repeatedly on a fresh batch each time. You compare two implementations: (A) maintain a min-heap of size K while scanning all N items, and (B) use Quickselect to partition around the K-th largest element, then sort only those K items. Which statement best captures the real trade-off between them?

Question

You are building a service that must return the top K highest-scoring items out of N items (N >> K), and the request arrives repeatedly on a fresh batch each time. You compare two implementations: (A) maintain a min-heap of size K while scanning all N items, and (B) use Quickselect to partition around the K-th largest element, then sort only those K items. Which statement best captures the real trade-off between them?

Accepted Answer

Min-heap kích thước K cho mỗi phần tử tốn tối đa O(log K) nên tổng là O(N log K), chỉ giữ K phần tử trong bộ nhớ và chạy được trên stream khi chưa biết N. Quickselect trung bình O(N) nhưng xấu nhất O(N^2) (trừ khi dùng median-of-medians) và cần toàn bộ mảng có thể sửa đổi trong RAM. Phương án B sai vì B không phải O(N log K) và không 'luôn tốt hơn'; C sai vì chi phí heap là log K chứ không phải log N; D sai vì Quickselect chuẩn không đảm bảo O(N) worst case và heap không bị suy biến thành O(N*K).

Câu hỏi hôm nay