Bài toán Top-k

Question

Cho một mảng chưa được sắp xếp nums có độ dài \(n\), hãy trả về \(k\) phần tử lớn nhất trong mảng.

Đối với bài toán này, trước hết chúng ta sẽ giới thiệu hai giải pháp tương đối đơn giản, sau đó là một giải pháp hiệu quả hơn sử dụng đống.

Phương pháp 1: Lựa chọn lặp

Chúng ta có thể thực hiện \(k\) vòng duyệt như được thể hiện trong hình dưới đây, trích xuất phần tử lớn thứ \(1\), thứ \(2\), \(\dots\), thứ \(k\) ở mỗi vòng, với độ phức tạp thời gian là \(O(nk)\).

Phương pháp này chỉ phù hợp khi \(k \ll n\), bởi vì khi \(k\) gần bằng \(n\), độ phức tạp thời gian sẽ tiệm cận \(O(n^2)\), khiến nó trở nên rất kém hiệu quả.

Tip

Khi \(k = n\), chúng ta có thể thu được một dãy đã được sắp xếp hoàn chỉnh, điều này tương đương với thuật toán "sắp xếp chọn" (selection sort).

Phương pháp 2: Sắp xếp

Như được thể hiện trong hình dưới đây, trước tiên chúng ta có thể sắp xếp mảng nums, sau đó trả về \(k\) phần tử ở ngoài cùng bên phải, với độ phức tạp thời gian là \(O(n \log n)\).

Rõ ràng, phương pháp này thực hiện nhiều công việc hơn mức cần thiết, vì chúng ta chỉ cần tìm \(k\) phần tử lớn nhất chứ không cần sắp xếp các phần tử còn lại.

Phương pháp 3: Đống

Chúng ta có thể giải quyết bài toán Top-k hiệu quả hơn bằng cách sử dụng đống, như được thể hiện trong hình dưới đây.

1. Khởi tạo một đống cực tiểu, trong đó phần tử ở đỉnh đống là nhỏ nhất.
2. Đầu tiên, lần lượt chèn \(k\) phần tử đầu tiên của mảng vào đống.
3. Bắt đầu từ phần tử thứ \((k + 1)\), nếu phần tử hiện tại lớn hơn phần tử ở đỉnh đống, loại bỏ phần tử ở đỉnh đống và chèn phần tử hiện tại vào đống.
4. Sau khi hoàn thành thao tác duyệt, đống sẽ chứa \(k\) phần tử lớn nhất.

<1><2><3><4><5><6><7><8><9>

Mã nguồn triển khai như sau:

[file]{top_k}-[class]{}-[func]{top_k_heap}

Tổng cộng có \(n\) vòng chèn và loại bỏ khỏi đống được thực hiện, với độ dài tối đa của đống là \(k\), do đó độ phức tạp thời gian là \(O(n \log k)\). Phương pháp này rất hiệu quả; khi \(k\) nhỏ, độ phức tạp thời gian tiệm cận \(O(n)\); khi \(k\) lớn, độ phức tạp thời gian không vượt quá \(O(n \log n)\).

Ngoài ra, phương pháp này rất phù hợp với luồng dữ liệu động. Khi dữ liệu mới truyền đến, chúng ta có thể liên tục duy trì các phần tử trong đống, cho phép cập nhật động \(k\) phần tử lớn nhất.