Hướng Dẫn Chi Tiết Về Kỹ Thuật Two Heaps Để Tìm Giá Trị Trung Bình

1. Giới Thiệu Kỹ Thuật Two Heaps

Kỹ thuật Two Heaps là một phương pháp hiệu quả sử dụng hai cấu trúc dữ liệu heap (đống) nhằm duy trì và xử lý dữ liệu một cách linh hoạt. Phương pháp này thường được áp dụng để xác định giá trị trung bình (median) của một tập dữ liệu động, giúp ích rất nhiều trong nhiều lĩnh vực ứng dụng khác nhau.

Ứng Dụng Thực Tế Của Two Heaps

• Duy trì giá trị trung bình trong các luồng dữ liệu động, chẳng hạn như trong các 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, như trong các 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 Của Kỹ Thuật Two Heaps

Hai cấu trúc dữ liệu chính trong phương pháp này là:

1. Max Heap (Đống Tối Đa): Duy trì nửa nhỏ hơn của dữ liệu, với phần tử lớn nhất nằm ở đỉnh heap.
2. Min Heap (Đống Tối Thiểu): Duy trì nửa lớn hơn của dữ liệu, với phần tử nhỏ nhất ở đỉnh heap.

Cách Hoạt Động

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

3. Cài Đặt Kỹ Thuật Two Heaps Trong Python

Dưới đây là một đoạn mã minh họa cách triển khai thuật toán Two Heaps để tìm giá trị trung bình từ một luồng dữ liệu:

import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []  # Max Heap lưu số âm
        self.min_heap = []  # Min Heap

    def add_num(self, num):
        # Thêm vào Max Heap đầu tiên
        heapq.heappush(self.max_heap, -num)
        
        # Đảm bảo rằng phần tử lớn nhất trong Max Heap nhỏ hơn phần tử nhỏ nhất trong 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))
        
        # Cân bằng kích thước của hai heap
        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

# Ví Dụ 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 bình là: {mf.find_median()}")

Giải Thích Mã Lệnh

• heapq.heappush(): Là hàm dùng để thêm phần tử vào heap.
• Sử dụng số âm cho self.max_heap để mô phỏng max heap trong Python, vì thư viện heapq chỉ hỗ trợ min heap.
• Cân bằng giữa hai heap bằng cách di chuyển các phần tử giữa chúng khi cần thiết.
• find_median() trả về giá trị trung bình dựa trên kích thước của hai heap.

4. Độ Phức Tạp Thời Gian

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

5. Tổng Kết

Kỹ thuật Two Heaps là một giải pháp mạnh mẽ và hiệu quả để duy trì giá trị trung bình của dữ liệu động. Bằng cách sử dụng cả Max Heap và Min Heap, chúng ta có thể giữ nửa nhỏ và nửa lớn của dữ liệu một cách hiệu quả. Phương pháp này rất hữu ích cho bài toán tìm giá trị trung bình với độ phức tạp O(log N) cho mỗi thao tác thêm dữ liệu. Bạn có thể áp dụng thuật toán này vào nhiều hệ thống theo dõi dữ liệu theo thời gian thực!

source: viblo