Cấu trúc dữ liệu và Giải thuật Bài 39: Khuôn mẫu Top K Elements bằng cấu trúc Heap.

Khi vận hành các hệ thống backend chịu tải cao, bạn sẽ hiếm khi được yêu cầu sắp xếp toàn bộ cơ sở dữ liệu. Thay vào đó, bài toán thực tế luôn mang dáng dấp của việc trích xuất một nhóm nhỏ tinh hoa từ một luồng dữ liệu khổng lồ: "Top 10 sản phẩm bán chạy nhất Hasaki tháng này", "Top 5 IP đang spam request nhiều nhất", hoặc "Top 3 điểm cảm biến đo nhiệt độ cao nhất trên Metro Line 1".

Đây là dạng toán Top K Elements. Nếu không có cấu trúc dữ liệu phù hợp, bài toán này sẽ nhanh chóng vắt kiệt CPU và RAM của hệ thống.

1. Vết xe đổ của thuật toán Sắp xếp (Sorting)

Phản xạ tự nhiên nhất để tìm Top $K$ phần tử lớn nhất là mang toàn bộ mảng đi sắp xếp giảm dần, sau đó cắt lấy $K$ phần tử đầu tiên.

• Thời gian: $O(n \log n)$

• Không gian: Có thể lên tới $O(n)$ tùy thuật toán.

Hãy tưởng tượng luồng dữ liệu log (Data Stream) trả về 100 triệu bản ghi, nhưng bạn chỉ cần tìm 10 bản ghi có độ trễ (latency) cao nhất. Việc bắt hệ thống phải so sánh và sắp xếp hoàn chỉnh cả 99.999.990 bản ghi còn lại là một sự lãng phí tài nguyên khủng khiếp. Tệ hơn nữa, nếu dữ liệu truyền đến liên tục (Streaming) mà không có điểm dừng, bạn thậm chí không thể có một mảng tĩnh để mà sắp xếp.

2. Tư duy ngược: Dùng Min Heap để tìm Top K lớn nhất

Để giải quyết bài toán với luồng dữ liệu vô tận, chúng ta áp dụng một nghịch lý toán học cực kỳ thanh lịch: Dùng Min Heap (Đống Nhỏ Nhất) để tìm ra các phần tử Lớn Nhất.

Thay vì lưu trữ toàn bộ dữ liệu, chúng ta chỉ duy trì một Min Heap có kích thước cố định đúng bằng $K$. Heap này đóng vai trò như một "phòng VIP" chỉ chứa $K$ phần tử lớn nhất từng được duyệt qua.

Luật vận hành của "Phòng VIP":

1. Gác cổng (Root của Min Heap): Vì đây là Min Heap, phần tử nằm ở đỉnh (Root) luôn là phần tử nhỏ nhất trong số $K$ phần tử đang nằm trong phòng VIP. Kẻ yếu nhất này sẽ làm nhiệm vụ gác cổng.

2. Khám phá dữ liệu: Duyệt qua từng phần tử của mảng khổng lồ.

3. So sánh và Đào thải: Nếu phần tử đang xét lớn hơn "kẻ gác cổng" (Root), điều đó chứng tỏ kẻ gác cổng không còn xứng đáng nằm trong Top $K$ nữa. Ta lập tức Pop kẻ gác cổng ra khỏi Heap, và Push phần tử mới vào. Heap sẽ tự động "vun đống" (Heapify) trong thời gian $O(\log k)$ để đẩy một kẻ yếu nhất mới lên làm gác cổng.

4. Nếu phần tử đang xét nhỏ hơn hoặc bằng kẻ gác cổng, nó bị loại ngay lập tức mà không cần tốn thêm chu kỳ CPU nào.

Kết thúc quá trình duyệt, $K$ phần tử trụ lại được trong Min Heap chính là Top $K$ phần tử lớn nhất của toàn bộ mảng.

Phân tích độ phức tạp:

• Thời gian: $O(n \log k)$. Vì $k$ thường rất nhỏ (ví dụ $k = 10$), $\log k$ gần như là hằng số. Thuật toán tiệm cận tốc độ ánh sáng $O(n)$.

• Không gian: $O(k)$. Dù mảng có 1 tỷ phần tử, hệ thống cũng chỉ tốn dung lượng RAM bằng đúng $K$ ô nhớ.

3. Triển khai chuẩn mực bằng Golang

Khác với Bài 38 (tự viết tay hàm heapifyUp và heapifyDown), khi viết backend thực tế bằng Go, các kỹ sư luôn sử dụng package container/heap của Standard Library.

Để dùng package này, bạn cần khai báo một kiểu dữ liệu tùy chỉnh (ví dụ: MinHeap) và thỏa mãn interface sort.Interface (gồm 3 hàm Len, Less, Swap), cộng thêm 2 hàm Push và Pop với pointer receiver.

Go

package main

import (
    "container/heap"
    "fmt"
)

// 1. Định nghĩa kiểu dữ liệu MinHeap dựa trên Slice
type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] } // Dấu < quyết định đây là Min Heap
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

// Push dùng Pointer Receiver vì nó thay đổi kích thước Slice
func (h *MinHeap) Push(x any) {
    *h = append(*h, x.(int))
}

// Pop lấy phần tử cuối cùng của Slice (container/heap đã tự động đưa Root xuống cuối)
func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// Hàm giải quyết bài toán Top K
func findTopK(nums []int, k int) []int {
    h := &MinHeap{}
    heap.Init(h)
    
    for _, num := range nums {
        heap.Push(h, num)
        
        // Giữ kích thước Heap luôn ở mức K
        if h.Len() > k {
            heap.Pop(h) // Loại bỏ kẻ nhỏ nhất trong phòng VIP
        }
    }
    
    return *h
}

4. Khuôn mẫu K-Way Merge (Mở rộng từ Top K)

Khuôn mẫu Top K Elements bằng Heap mạnh mẽ đến mức nó đẻ ra một nhánh thuật toán nâng cao mang tên K-Way Merge.

Giả sử hệ thống xử lý đơn hàng của bạn được chia thành 5 worker độc lập, mỗi worker trả về một file danh sách giao dịch đã được sắp xếp tăng dần. Nhiệm vụ của bạn là gộp 5 file này lại thành một danh sách sắp xếp duy nhất.

Thay vì gộp tất cả rồi dùng Quick Sort $O(n \log n)$, bạn chỉ cần:

1. Đưa 5 phần tử đầu tiên của 5 file vào một Min Heap (kích thước $K=5$).

2. Pop phần tử nhỏ nhất từ Heap ra ghi vào file kết quả.

3. Phần tử vừa Pop thuộc về file nào, lập tức đọc phần tử tiếp theo của file đó và Push vào Heap.

4. Lặp lại cho đến khi cả 5 file cạn kiệt dữ liệu.

Khuôn mẫu này gánh vác toàn bộ hạ tầng xử lý của các hệ quản trị cơ sở dữ liệu lớn (như Cassandra, Elasticsearch) khi thực hiện các truy vấn phân tán (Distributed Queries) trên nhiều shard khác nhau.

Chúng ta đã chính thức khép lại hành trình làm chủ các cấu trúc dữ liệu mảng tuyến tính và dạng ngăn xếp/hàng đợi. Từ bài học tiếp theo, tư duy thuật toán sẽ bước sang một chiều không gian phi tuyến tính, nơi dữ liệu phân nhánh như rễ cây và liên kết với nhau thành các mạng lưới phức tạp.