Heap (đống) là một cấu trúc dữ liệu cây đặc biệt, đóng vai trò quan trọng trong việc quản lý tập hợp các phần tử có thứ tự. Một Heap hợp lệ phải tuân thủ hai quy tắc cốt lõi:

• Tính chất cây nhị phân hoàn chỉnh: Cấu trúc cây phải được lấp đầy ở tất cả các tầng ngoại trừ tầng cuối cùng, nơi các nút phải được sắp xếp từ trái sang phải.
• Tính chất Heap (Heap Property): Giá trị của mỗi nút cha luôn lớn hơn hoặc bằng (Max Heap) hoặc nhỏ hơn hoặc bằng (Min Heap) giá trị của các nút con.

Triển khai Max Heap bằng mảng

Trong thực tế, người ta thường sử dụng mảng để biểu diễn Heap vì tính hiệu quả về bộ nhớ. Với một phần tử tại vị trí k trong mảng:

• Con trái nằm tại: 2k + 1
• Con phải nằm tại: 2k + 2
• Nút cha nằm tại: floor((k - 1) / 2)

class MaxHeap:
    def __init__(self):
        self.data = []

    def them_phan_tu(self, gia_tri):
        self.data.append(gia_tri)
        self._day_len(len(self.data) - 1)

    def lay_max(self):
        if not self.data: return None
        if len(self.data) == 1: return self.data.pop()
        
        max_val = self.data[0]
        self.data[0] = self.data.pop()
        self._day_xuong(0)
        return max_val

    def _day_len(self, idx):
        while idx > 0:
            cha = (idx - 1) // 2
            if self.data[idx] > self.data[cha]:
                self.data[idx], self.data[cha] = self.data[cha], self.data[idx]
                idx = cha
            else:
                break

    def _day_xuong(self, idx):
        while True:
            trai, phai = 2 * idx + 1, 2 * idx + 2
            lon_nhat = idx
            if trai < len(self.data) and self.data[trai] > self.data[lon_nhat]:
                lon_nhat = trai
            if phai < len(self.data) and self.data[phai] > self.data[lon_nhat]:
                lon_nhat = phai
            if lon_nhat != idx:
                self.data[idx], self.data[lon_nhat] = self.data[lon_nhat], self.data[idx]
                idx = lon_nhat
            else:
                break

Sử dụng module heapq trong Python

Thư viện chuẩn heapq của Python cung cấp bộ công cụ tối ưu để thao tác với Min Heap. Dưới đây là cách sử dụng các phương thức phổ biến:

import heapq

# Khởi tạo danh sách
ds = [5, 2, 8, 1, 9]
heapq.heapify(ds) # Chuyển đổi danh sách thành Min Heap

# Thêm phần tử
heapq.heappush(ds, 0)

# Lấy phần tử nhỏ nhất
nho_nhat = heapq.heappop(ds)

# Thay thế và lấy phần tử nhỏ nhất trong một bước
min_val = heapq.heapreplace(ds, 10)

# Tìm n phần tử lớn nhất/nhỏ nhất
top_3_lon = heapq.nlargest(3, ds)
top_3_nho = heapq.nsmallest(3, ds)

Cấu trúc dữ liệu Heap là nền tảng của nhiều thuật toán quan trọng như Heap Sort (độ phức tạp O(n log n)) và các bài toán hàng đợi ưu tiên (Priority Queue), giúp duy trì hiệu suất xử lý dữ liệu cao trong các hệ thống thời gian thực.