Phỏng vấn

Mẫu Top K phần tử bằng Heap trong phỏng vấn, so sánh với Quickselect

Khi cần tìm K phần tử lớn nhất, điểm gần gốc tọa độ nhất hoặc từ khóa xuất hiện nhiều nhất trong tập dữ liệu lớn, việc sắp xếp toàn bộ mảng tốn O(n log n) là dư thừa. Duy trì một Min-Heap có kích thước tối đa K giúp bạn giữ đúng K ứng viên mạnh nhất với thời gian O(n log k) và bộ nhớ phụ chỉ O(k).

Nhận diện nhóm bài Top K và hợp đồng cần chốt với người phỏng vấn

Trong các vòng phỏng vấn thuật toán lẫn thiết kế hệ thống (System Design), bài toán trích xuất K phần tử đứng đầu (Top K Elements) xuất hiện liên tục dưới nhiều hình thức:

  • Kth Largest Element in an Array: Tìm phần tử lớn thứ k trong mảng chưa sắp xếp.
  • Top K Frequent Elements / Words: Tìm k giá trị (hoặc từ vựng) có tần suất xuất hiện cao nhất.
  • K Closest Points to Origin: Tìm k điểm trên mặt phẳng tọa độ có khoảng cách Euclid tới gốc (0, 0) nhỏ nhất.
  • Kth Largest Element in a Stream: Duy trì phần tử lớn thứ k khi dữ liệu chảy vào liên tục theo thời gian thực.

Trước khi chọn giải pháp giữa Sắp xếp toàn bộ, Heap kích thước k, Quickselect hay Bucket Sort, bạn nên hỏi rõ người phỏng vấn 4 điểm định hình lời giải:

  1. Định nghĩa "lớn thứ k" khi có phần tử trùng nhau: Với mảng [3, 2, 3, 1, 2, 4, 5, 5, 6] và k = 4, sau khi sắp giảm dần thành [6, 5, 5, 4, 3, 3, 2, 2, 1], phần tử lớn thứ 4 tính theo chỉ số sau khi sắp (tức là số 4) hay tính theo các giá trị phân biệt? Trong 99% đề chuẩn (như LeetCode 215), đề bài tính theo thứ tự sau khi sắp xếp không giảm (bao gồm cả bản sao).
  2. Dữ liệu tĩnh trong bộ nhớ hay luồng dữ liệu trực tuyến (streaming)? Nếu dữ liệu là luồng vô tận hoặc mảng quá lớn không vừa RAM, bạn không thể dùng Quickselect (vì cần truy cập ngẫu nhiên toàn bộ mảng) mà bắt buộc phải dùng Heap kích thước k.
  3. Có được phép sửa đổi mảng đầu vào không? Thuật toán chọn nhanh Hoare (Quickselect) đạt trung bình O(n) với O(1) bộ nhớ phụ nhưng sẽ tráo đổi các phần tử ngay trên mảng gốc.
  4. Quan hệ giữa k và n: Nếu k rất nhỏ so với n (ví dụ tìm Top 10 bài viết từ 10 triệu bản ghi), O(n log k) bằng Heap cực kỳ lợi thế; nếu k xấp xỉ n / 2, Quickselect hoặc Bucket Sort sẽ được hỏi tới ở phần mở rộng.
Ý chính

Quy tắc chọn loại Heap cho bài toán Top K luôn ngược với tên gọi: để giữ K phần tử lớn nhất, hãy dùng Min-Heap kích thước k; để giữ K phần tử nhỏ nhất, hãy dùng Max-Heap kích thước k. Đỉnh của Heap đóng vai trò là "người gác cổng" yếu nhất trong nhóm Top K hiện tại: bất kỳ ứng viên mới nào vượt qua được người gác cổng đều xứng đáng thế chỗ vào nhóm.

Mẫu Top K bằng Min-Heap cỡ K: tìm K = 4 số lớn nhất Mảng [3, 2, 3, 1, 2, 4, 5, 5, 6] · Đỉnh Min-Heap giữ phần tử lớn thứ 4 Min-Heap cỡ K = 4 cuối cùng 4 ← top() = K-th 5 5 6 1. Nạp 4 phần tử đầu [3, 2, 3, 1] Heap = [1, 2, 3, 3] · ngưỡng top() = 1 2. Quét 2, 4, 5, 5, 6 (so với top) Mỗi khi x > top(): pop() kẻ yếu nhất, push(x) 3. Kết quả: top() = 4 Thời gian O(n log k) · Bộ nhớ O(k)
Top K bằng Min-Heap cỡ K = 4 Mảng [3, 2, 3, 1, 2, 4, 5, 5, 6] 1. Khởi tạo 4 số đầu: [1, 2, 3, 3] Đỉnh Min-Heap giữ ngưỡng nhỏ nhất: top = 1 2. Quét tiếp 2, 4, 5, 5, 6 Nếu x > top: pop đỉnh cũ, push(x) vào Heap 3. Min-Heap cuối: [4, 5, 5, 6] Số lớn thứ 4 nằm ngay ở đỉnh: top() = 4 Heap: O(n log k) · Quickselect: O(n) TB
Hình 1. Duy trì Min-Heap kích thước k = 4 khi quét qua mảng nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]: nạp 4 số đầu thành Heap [1, 2, 3, 3], sau đó mỗi số lớn hơn đỉnh Heap đẩy phần tử nhỏ nhất ra ngoài; cuối cùng Heap còn [4, 5, 5, 6] và đỉnh giữ đúng phần tử lớn thứ 4 là 4.

Tại sao tìm K phần tử lớn nhất lại dùng Min-Heap thay vì Max-Heap?

Khi nghe đề bài "tìm phần tử lớn thứ k", phản xạ tự nhiên của nhiều ứng viên là đẩy tất cả n phần tử vào một Max-Heap rồi gọi lệnh pop() đúng k lần. Cách đó đúng và tốn thời gian O(n + k log n) (nếu dựng Heap dưới lên bằng heapify), nhưng lại cần tới O(n) bộ nhớ để chứa toàn bộ mảng trong Heap.

Ngược lại, nếu ta chỉ duy trì một Min-Heap chứa tối đa k phần tử lớn nhất đã từng gặp tính đến thời điểm hiện tại:

  • Phần tử nằm ở đỉnh Min-Heap (min_heap.top()) là phần tử nhỏ nhất trong số k phần tử lớn nhất, tức là ứng viên đang giữ vị trí lớn thứ k tạm thời.
  • Khi xét phần tử mới x:
    • Nếu min_heap.size() < k: nhóm Top K chưa đủ chỗ, ta đẩy thẳng x vào Heap.
    • Nếu min_heap.size() == k và x <= min_heap.top(): vì x còn không thắng nổi phần tử nhỏ nhất trong nhóm k anh dẫn đầu, x chắc chắn không có cơ hội lọt vào Top K (chỉ mất O(1) để bỏ qua!).
    • Nếu min_heap.size() == k và x > min_heap.top(): x xứng đáng vào Top K hơn phần tử ở đỉnh, nên ta loại bỏ đỉnh cũ (pop) và đưa x vào (push).

Sau khi quét hết n phần tử, Min-Heap chứa đúng k phần tử lớn nhất của cả mảng, và đỉnh min_heap.top() chính là phần tử lớn thứ k.

Chạy tay từng bước trên nums = [3, 2, 1, 5, 6, 4], k = 2

Hãy theo dõi trạng thái của Min-Heap cỡ k = 2 khi duyệt qua từng phần tử của mảng [3, 2, 1, 5, 6, 4]:

Bước Phần tử x Kích thước Heap trước bước So sánh với top() Thao tác thực hiện Min-Heap sau bước (đỉnh ở đầu)
1 3 0 < 2 Chưa đủ k phần tử push(3) [3] (top = 3)
2 2 1 < 2 Chưa đủ k phần tử push(2) [2, 3] (top = 2)
3 1 2 == 2 1 <= top (2) Bỏ qua trong O(1) [2, 3] (top = 2)
4 5 2 == 2 5 > top (2) pop() bỏ 2, push(5) [3, 5] (top = 3)
5 6 2 == 2 6 > top (3) pop() bỏ 3, push(6) [5, 6] (top = 5)
6 4 2 == 2 4 <= top (5) Bỏ qua trong O(1) [5, 6] (top = 5)

Kết thúc vòng quét, hai phần tử lớn nhất của mảng là 5 và 6 nằm gọn trong Heap, và đỉnh min_heap.top() = 5 là câu trả lời chính xác cho phần tử lớn thứ 2.

Code mẫu C++17, Python và Java 21

Chương trình dưới đây cài đặt thuật toán tìm phần tử lớn thứ k bằng Min-Heap kích thước k trên cả 3 ngôn ngữ. Khi chạy không có đầu vào từ stdin, chương trình tự động kiểm tra bộ mẫu nums = [3, 2, 1, 5, 6, 4], k = 2 và in ra 5.

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = 6, k = 2;
    vector<long long> nums = {3, 2, 1, 5, 6, 4};
    if (cin >> n >> k) {
        nums.resize(n);
        for (auto& x : nums) cin >> x;
    }
    priority_queue<long long, vector<long long>, greater<long long>> min_heap;
    for (long long x : nums) {
        if ((int)min_heap.size() < k) {
            min_heap.push(x);
        } else if (x > min_heap.top()) {
            min_heap.pop();
            min_heap.push(x);
        }
    }
    cout << min_heap.top() << '\n';
    return 0;
}

Trong bản Python, khi len(min_heap) == k và x > min_heap[0], ta dùng hàm heapq.heapreplace(min_heap, x) (hoặc heappushpop). Hàm này thay trực tiếp gốc của Heap bằng x rồi vun đống xuống (sift-down) chỉ trong một lượt, nên ít phép so sánh hơn việc gọi rời hai lệnh heappop rồi heappush.

Độ phức tạp và khác biệt mặc định của Priority Queue giữa 3 ngôn ngữ

  • Thời gian: O(n log k) trong trường hợp xấu nhất (khi mảng đầu vào tăng dần, mọi phần tử đều lớn hơn top() và kích hoạt pop/push trên Heap cỡ k). Nếu thứ tự dữ liệu ngẫu nhiên (các giá trị khác nhau), phần tử thứ i (với i > k) chỉ lớn hơn top() khi nó thuộc nhóm k số lớn nhất của i số đầu tiên, xác suất là k / i. Vì vậy đa số phần tử bị bỏ qua trong O(1), số lần pop/push kỳ vọng chỉ khoảng k · ln(n / k), và thời gian kỳ vọng là O(n + k log k · (1 + log(n / k))).
  • Bộ nhớ phụ: O(k) — chỉ lưu tối đa k phần tử trong Heap tại mọi thời điểm.
  • Khác biệt mặc định giữa C++, Python và Java (rất hay bị hỏi trong phỏng vấn):
    • Trong C++17, std::priority_queue<T> mặc định là Max-Heap! Để biến thành Min-Heap, bạn phải khai báo đủ 3 tham số mẫu: priority_queue<long long, vector<long long>, greater<long long>>.
    • Trong Python (heapq) và Java 21 (java.util.PriorityQueue), cấu trúc mặc định lại là Min-Heap! Khi cần Max-Heap trong Python, từ Python 3.14 bạn dùng thẳng heapq.heappush_max / heapq.heappop_max; với bản cũ hơn, mẹo quen thuộc với số nguyên là đổi dấu -x trước khi đẩy vào; còn trong Java 21, bạn khởi tạo new PriorityQueue<>(Collections.reverseOrder()) hoặc truyền biểu thức lambda (a, b) -> Long.compare(b, a).

So sánh 5 chiến lược giải bài toán Top K trong phỏng vấn

Khi người phỏng vấn hỏi tiếp: "Em còn cách nào giảm độ phức tạp xuống O(n) không?", bạn có thể trình bày bảng đối chiếu 5 phương pháp dưới đây để thể hiện chiều sâu kiến thức:

Phương pháp Thời gian trung bình Thời gian xấu nhất Bộ nhớ phụ Khi nào là lựa chọn tốt nhất?
Sắp xếp toàn bộ (Full Sort) O(n log n) O(n log n) O(1) đến O(n) Khi n nhỏ (<= 10^4) hoặc đằng nào cũng cần toàn bộ mảng theo thứ tự sắp xếp
Min-Heap kích thước k O(n log k) O(n log k) O(k) Khi k << n, khi dữ liệu là luồng trực tuyến (stream), hoặc không được sửa mảng gốc
Max-Heap heapify toàn mảng O(n + k log n) O(n + k log n) O(n) Khi đã có sẵn mảng trong bộ nhớ, được dùng O(n) không gian và k rất nhỏ
Quickselect (Phân hoạch Hoare) O(n) O(n²) (nếu chọn chốt kém) O(1) Khi toàn bộ mảng nằm trong RAM, được phép tráo đổi tại chỗ và cần tối ưu thời gian kỳ vọng
Bucket Sort theo tần suất O(n) O(n) O(n) Dành riêng cho bài Top K Frequent Elements vì tần suất của mỗi phần tử chỉ nằm trong đoạn [1..n]

Với bài Top K Frequent Elements (tìm k số xuất hiện nhiều nhất), sau khi đếm tần suất bằng bảng băm trong O(n), bạn vừa có thể đẩy các cặp (freq, num) vào Min-Heap cỡ k để đạt O(n log k), vừa có thể tạo mảng các thùng buckets[1..n] (trong đó buckets[f] chứa danh sách các số xuất hiện đúng f lần) rồi quét ngược từ f = n về 1 để nhặt đủ k phần tử trong đúng O(n) xác định.

Các lỗi sai phổ biến và cách tự kiểm tra code

  1. Dùng nhầm Max-Heap kích thước k khi tìm K phần tử lớn nhất: Nếu bạn dùng Max-Heap và mỗi khi kích thước vượt k lại gọi pop(), phần tử bị văng ra khỏi Heap chính là phần tử lớn nhất, nên cuối cùng Heap của bạn chỉ còn lại k phần tử nhỏ nhất!
  2. Không kiểm tra x > min_heap.top() mà luôn push(x) rồi pop(): Cách viết min_heap.push(x); if (min_heap.size() > k) min_heap.pop(); vẫn cho kết quả đúng, nhưng khi x <= min_heap.top(), bạn vẫn tốn O(log k) để đẩy x vào rồi lập tức lấy chính x ra. Kiểm tra if (x > min_heap.top()) trước giúp bỏ qua ngay trong O(1) và không bao giờ để kích thước Heap vượt lên k + 1.
  3. Tính căn bậc hai sqrt(x*x + y*y) trong bài K Closest Points: Hàm sqrt số thực vừa chậm vừa dễ sai số làm tròn; bạn chỉ cần so sánh bình phương khoảng cách 1LL * x * x + 1LL * y * y trên kiểu số nguyên 64-bit long long.

Để tự kiểm tra code trước khi kết thúc bài làm, bạn có thể viết một hàm đối chiếu chỉ 2 dòng (sắp xếp mảng giảm dần rồi lấy nums[k - 1]) và chạy thử trên 4 ca biên:

  • k = 1 (tìm phần tử lớn nhất) và k = n (tìm phần tử nhỏ nhất của mảng, ví dụ n = 5, k = 5 trên [-1, -5, 0, 3, 2] → phải trả về -5).
  • Mảng chỉ có đúng 1 phần tử (n = 1, k = 1, nums = [42] → trả về 42).
  • Mảng có nhiều phần tử trùng nhau quanh vị trí thứ k (nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4 → trả về 4).
  • Mảng toàn số nguyên âm để chắc chắn bạn không khởi tạo biến chốt bằng 0.

Luyện ngay trên Big-O Coding

Bạn hãy thực hành ngay 3 bài toán sử dụng cấu trúc dữ liệu Heap và chọn phần tử lớn thứ K trong lộ trình Coding Interview 150 dưới đây.

Câu hỏi thường gặp

Tại sao Quickselect có độ phức tạp trung bình là O(n) chứ không phải O(n log n) như Quicksort?

Trong Quicksort, sau khi phân hoạch mảng quanh phần tử chốt (pivot), ta phải đệ quy xuống cả hai nửa trái và phải nên tổng chi phí là \(n + 2 \cdot (n/2) + \dots = O(n \log n)\). Ngược lại, trong Quickselect, ta biết chính xác chỉ số \(k\) cần tìm nằm ở bên trái hay bên phải chốt, nên ta chỉ đệ quy vào đúng một nửa chứa vị trí \(k\) và bỏ hẳn nửa kia. Tổng số phép so sánh trung bình là chuỗi hình học \(n + n/2 + n/4 + n/8 + \dots \le 2n = O(n)\).

Trong bài Top K Frequent Words, nếu hai từ có cùng tần suất nhưng đề yêu cầu ưu tiên từ có thứ tự từ điển nhỏ hơn thì viết bộ so sánh cho Min-Heap thế nào?

Vì Min-Heap sẽ loại bỏ phần tử "yếu nhất" ở đỉnh khi đầy, bạn phải định nghĩa phần tử "yếu hơn" là phần tử có tần suất nhỏ hơn, hoặc nếu cùng tần suất thì có thứ tự từ điển lớn hơn (ví dụ "love" đứng sau "i" nên "love" bị loại trước để giữ lại "i"). Khi kết thúc và lấy các từ ra khỏi Min-Heap, bạn chỉ cần đảo ngược danh sách kết quả là có thứ tự từ mạnh nhất đến yếu nhất.

Làm sao tìm trung vị của luồng dữ liệu (Find Median from Data Stream) bằng hai Heap?

Đó là mở rộng kinh điển của mẫu Top K: bạn chia các số đã đọc thành hai nửa bằng nhau. Nửa nhỏ hơn được lưu trong một Max-Heap lo, nửa lớn hơn được lưu trong một Min-Heap hi, giữ bất biến 0 <= lo.size() - hi.size() <= 1. Khi đó trung vị luôn nằm ngay ở đỉnh lo.top() (nếu tổng số phần tử lẻ) hoặc là trung bình cộng của hai đỉnh (lo.top() + hi.top()) / 2.0 (nếu chẵn) trong thời gian truy vấn O(1) và thêm mới O(log n).

Muốn học bài bản cùng giảng viên?

Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483