Hướng Dẫn Two Heaps Cho Người Mới Bắt Đầu

1. Giới Thiệu

Two Heaps là một kỹ thuật sử dụng hai heap (đống) để duy trì và xử lý dữ liệu hiệu quả, thường được dùng để tìm giá trị trung vị (median) của một tập dữ liệu động.

Ứng Dụng Thực Tế:

• Duy trì giá trị trung vị trong luồng dữ liệu động (ví dụ: hệ thống theo dõi giá cổ phiếu theo thời gian thực).
• Quản lý hàng đợi ưu tiên, chẳng hạn như hệ thống xếp hạng trong trò chơi hoặc quản lý tác vụ.

2. Nguyên Lý Hoạt Động

Two Heaps sử dụng hai cấu trúc dữ liệu chính:

1. Max Heap (Heap tối đa): Lưu trữ nửa nhỏ hơn của dữ liệu. Phần tử lớn nhất nằm trên đỉnh heap.
2. Min Heap (Heap tối thiểu): Lưu trữ nửa lớn hơn của dữ liệu. Phần tử nhỏ nhất nằm trên đỉnh heap.

Cách hoạt động:

• Khi một phần tử mới được thêm vào, ta đưa nó vào Max Heap nếu nhỏ hơn trung vị hiện tại, hoặc vào Min Heap nếu lớn hơn.
• Đảm bảo hai heap có kích thước cân bằng hoặc chênh lệch tối đa 1 phần tử.
• Trung vị sẽ nằm ở đỉnh của Max Heap (nếu số lượng phần tử lẻ) hoặc là trung bình của hai đỉnh heap (nếu số lượng phần tử chẵn).

3. Cài Đặt Two Heaps Trong Python

Dưới đây là cách triển khai thuật toán Two Heaps để tìm trung vị của một luồng dữ liệu:

import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []  # Heap tối đa (lưu số âm để sử dụng heapq như max heap)
        self.min_heap = []  # Heap tối thiểu

    def add_num(self, num):
        # Thêm vào max heap trước
        heapq.heappush(self.max_heap, -num)
        
        # Đảm bảo phần tử lớn nhất của max_heap nhỏ hơn phần tử nhỏ nhất của min_heap
        if self.max_heap and self.min_heap and (-self.max_heap[0] > self.min_heap[0]):
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        
        # Đảm bảo hai heap có kích thước cân bằng
        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        elif len(self.min_heap) > len(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def find_median(self):
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        return (-self.max_heap[0] + self.min_heap[0]) / 2.0

# Sử dụng MedianFinder
mf = MedianFinder()
nums = [5, 15, 1, 3]
for num in nums:
    mf.add_num(num)
    print(f"Sau khi thêm {num}, trung vị là: {mf.find_median()}")

Giải Thích Code:

• heapq.heappush(): Thêm phần tử vào heap.
• self.max_heap lưu số âm để giả lập Max Heap trong Python.
• Cân bằng hai heap bằng cách di chuyển phần tử giữa chúng.
• find_median() trả về trung vị dựa trên kích thước của hai heap.

4. Độ Phức Tạp

• Thêm một phần tử: O(log N) (vì cần điều chỉnh heap)
• Tìm trung vị: O(1) (chỉ cần truy cập đỉnh heap)

5. Tổng Kết

• Two Heaps là một kỹ thuật mạnh mẽ để duy trì trung vị của dữ liệu động.
• Sử dụng Max Heap và Min Heap để giữ nửa nhỏ và nửa lớn của dữ liệu.
• Hiệu quả cho bài toán tìm trung vị với độ phức tạp O(log N) cho mỗi thao tác thêm dữ liệu.

Bạn có thể mở rộng thuật toán này để áp dụng vào các hệ thống theo dõi dữ liệu thời gian thực!