Ứng dụng Priority Queue, Max Heap, Min Heap
Đọc đi nhé
Ứng dụng Priority Queue, Max Heap, Min Heap trong tìm K phần tử đầu tiên
Khi giải các bài toán liên quan đến việc tìm K phần tử lớn nhất, K phần tử nhỏ nhất, phần tử lớn thứ K hoặc nhỏ thứ K, chúng ta thường nghĩ ngay đến việc sắp xếp toàn bộ mảng.
Tuy nhiên, nếu mảng có N phần tử nhưng chỉ cần tìm K phần tử, đặc biệt khi K rất nhỏ so với N, việc sort toàn bộ mảng là không tối ưu.
Đây là lúc Priority Queue và Heap phát huy tác dụng.
1. Bài toán
Cho một mảng:
[10, 5, 8, 20, 3, 7, 15, 1]Yêu cầu tìm K = 3 phần tử nhỏ nhất.
Kết quả:
[1, 3, 5]Cách đơn giản nhất là sort toàn bộ mảng:
[1, 3, 5, 7, 8, 10, 15, 20]Sau đó lấy 3 phần tử đầu tiên.
Độ phức tạp:
O(N log N)Nhưng chúng ta thực tế chỉ cần biết 3 phần tử nhỏ nhất, không cần sắp xếp toàn bộ N phần tử.
2. Priority Queue là gì?
Priority Queue là một cấu trúc dữ liệu mà phần tử được lấy ra dựa trên độ ưu tiên thay vì thứ tự thêm vào.
Queue thông thường:
First In → First OutPriority Queue:
Phần tử có priority cao nhất → được lấy ra trướcPriority Queue thường được triển khai bằng Heap.
Hai loại Heap phổ biến nhất là:
- Min Heap
- Max Heap
3. Min Heap
Trong Min Heap, phần tử nhỏ nhất luôn nằm ở root.
Ví dụ:
1
/ \
3 5
/ \ /
7 8 10Do đó:
peek() → lấy phần tử nhỏ nhất
poll() → xóa phần tử nhỏ nhấtĐộ phức tạp thông thường:
peek() → O(1)
insert() → O(log N)
poll() → O(log N)Min Heap phù hợp khi chúng ta liên tục cần lấy phần tử nhỏ nhất.
4. Max Heap
Trong Max Heap, phần tử lớn nhất luôn nằm ở root.
Ví dụ:
10
/ \
8 7
/ \
3 5Do đó:
peek() → lấy phần tử lớn nhất
poll() → xóa phần tử lớn nhấtĐộ phức tạp:
peek() → O(1)
insert() → O(log N)
poll() → O(log N)Max Heap phù hợp khi chúng ta cần liên tục lấy phần tử lớn nhất.
5. Tìm K phần tử nhỏ nhất bằng Max Heap
Đây là một pattern rất quan trọng khi làm thuật toán.
Muốn tìm:
K phần tử nhỏ nhấtchúng ta sử dụng:
Max HeapTại sao lại dùng Max Heap?
Giả sử K = 3, chúng ta muốn duy trì 3 phần tử nhỏ nhất đã gặp.
Trong 3 phần tử đó, phần tử nào là phần tử lớn nhất thì chính là phần tử tệ nhất.
Khi gặp một số nhỏ hơn nó, chúng ta loại phần tử lớn nhất ra và thêm số mới vào.
Vì vậy, chúng ta cần Max Heap để phần tử lớn nhất luôn nằm ở root.
6. Ví dụ
Cho:
arr = [10, 5, 8, 20, 3, 7, 15, 1]
K = 3Bắt đầu:
heap = []Thêm 10:
[10]Thêm 5:
[10, 5]Thêm 8:
[10, 5, 8]Hiện tại đã có đủ 3 phần tử.
Tiếp tục gặp 20.
Vì:
20 > 10nên 20 không thể thuộc 3 phần tử nhỏ nhất.
Ta bỏ qua nó.
Tiếp theo gặp 3.
3 < 1010 đang là phần tử lớn nhất trong 3 phần tử hiện tại nên loại 10.
Sau đó thêm 3:
[8, 5, 3]Tiếp tục gặp 7.
7 < 8Loại 8, thêm 7:
[7, 5, 3]Gặp 15:
15 > 7Bỏ qua.
Gặp 1:
1 < 7Loại 7, thêm 1:
[5, 3, 1]Cuối cùng chúng ta có:
[1, 3, 5]Đây chính là 3 phần tử nhỏ nhất.
7. Code Java
Trong Java, PriorityQueue mặc định là Min Heap:
PriorityQueue<Integer> minHeap = new PriorityQueue<>();Muốn tạo Max Heap:
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>(Collections.reverseOrder());Code tìm K phần tử nhỏ nhất:
public static List<Integer> findKSmallest(int[] arr, int k) {
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>(Collections.reverseOrder());
for (int num : arr) {
maxHeap.offer(num);
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
return new ArrayList<>(maxHeap);
}Điểm quan trọng nhất là:
if (maxHeap.size() > k) {
maxHeap.poll();
}Vì đây là Max Heap nên poll() sẽ loại phần tử lớn nhất.
Nhờ vậy Heap luôn chỉ chứa:
K phần tử nhỏ nhất8. Tìm K phần tử lớn nhất bằng Min Heap
Nếu bài toán ngược lại:
Tìm K phần tử lớn nhấtthì chúng ta sử dụng Min Heap.
Ví dụ:
arr = [10, 5, 8, 20, 3, 7, 15, 1]
K = 3Kết quả:
[10, 15, 20]Tại sao dùng Min Heap?
Chúng ta muốn giữ lại 3 phần tử lớn nhất.
Trong 3 phần tử đó, phần tử nhỏ nhất là phần tử tệ nhất.
Khi gặp một phần tử lớn hơn nó, chúng ta loại phần tử nhỏ nhất.
Min Heap giúp phần tử nhỏ nhất luôn nằm ở root.
9. Code Java tìm K phần tử lớn nhất
public static List<Integer> findKLargest(int[] arr, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : arr) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return new ArrayList<>(minHeap);
}Sau khi duyệt toàn bộ mảng:
Min Heap = K phần tử lớn nhất10. Pattern cần nhớ
Đây là pattern rất quan trọng khi làm bài với Heap:
- K phần tử nhỏ nhất → Max Heap
- K phần tử lớn nhất → Min Heap
- Kth smallest → Max Heap
- Kth largest → Min Heap
Cách nhớ:
Muốn K phần tử nhỏ nhất
Ta giữ:
K phần tử nhỏ nhấtCần loại:
Phần tử lớn nhấtVì vậy:
Max HeapMuốn K phần tử lớn nhất
Ta giữ:
K phần tử lớn nhấtCần loại:
Phần tử nhỏ nhấtVì vậy:
Min Heap11. Độ phức tạp
Giả sử:
N = số lượng phần tử
K = số phần tử cần tìmNếu sử dụng Sorting:
O(N log N)Nếu sử dụng Heap:
O(N log K)Vì Heap chỉ chứa tối đa K phần tử.
Space complexity:
O(K)Điều này đặc biệt hiệu quả khi:
K << NVí dụ:
N = 10,000,000
K = 100Chúng ta không cần sort 10 triệu phần tử.
Chỉ cần duy trì một Heap có tối đa 100 phần tử.
12. Ứng dụng thực tế
Pattern này xuất hiện rất nhiều trong các bài toán thực tế.
Top K users
Ví dụ hệ thống có 10 triệu user và cần tìm:
Top 100 user có score cao nhấtTa có thể sử dụng:
Min Heap size = 100Duyệt qua từng user:
User → HeapNếu Heap vượt quá 100 phần tử:
poll()để loại user có score thấp nhất.
Cuối cùng Heap chứa:
Top 100 usersTop K sản phẩm
Tìm:
10 sản phẩm bán chạy nhấtCó thể sử dụng:
Min Heap size = 10Top K bài viết
Tìm:
20 bài viết có nhiều lượt xem nhấtCó thể duy trì:
Min Heap size = 20K phần tử nhỏ nhất trong dữ liệu streaming
Nếu dữ liệu đến liên tục:
data → data → data → data → ...không nhất thiết phải lưu toàn bộ dữ liệu rồi sort.
Có thể duy trì một Heap có kích thước K.
Mỗi phần tử mới được đưa vào Heap và loại phần tử không còn thuộc Top K.
13. Tổng quát hóa cách tư duy
Khi gặp bài toán Top K, hãy tự hỏi hai câu:
Tôi muốn giữ K phần tử nào?
Sau đó:
Trong K phần tử đó, phần tử nào là phần tử tệ nhất?
Nếu muốn:
K phần tử nhỏ nhấtthì phần tử tệ nhất là:
Phần tử lớn nhất→ Max Heap
Nếu muốn:
K phần tử lớn nhấtthì phần tử tệ nhất là:
Phần tử nhỏ nhất→ Min Heap
Có thể nhớ bằng sơ đồ:
TOP K
|
+-------+-------+
| |
K nhỏ nhất K lớn nhất
| |
loại lớn nhất loại nhỏ nhất
| |
Max Heap Min Heap14. Kết luận
Priority Queue là một abstraction cho phép chúng ta lấy phần tử theo độ ưu tiên.
Heap là một cấu trúc dữ liệu phổ biến để triển khai Priority Queue.
Trong bài toán Top K, pattern quan trọng nhất cần nhớ là:
K smallest → Max Heap
K largest → Min HeapMục tiêu của chúng ta không phải là sort toàn bộ mảng mà chỉ duy trì K phần tử tốt nhất.
Vì vậy:
Sorting:
O(N log N)
Heap:
O(N log K)Khi K nhỏ hơn rất nhiều so với N, cách tiếp cận bằng Heap có thể tiết kiệm đáng kể thời gian và bộ nhớ.
💬 Bình luận (0)