Cấu trúc dữ liệu và Giải thuật Bài 38: Hàng đợi ưu tiên (Priority Queue) và cấu trúc Heap (Min/Max Heap).

Trong bài học trước, Hàng đợi (Queue) đã hoàn thành xuất sắc nhiệm vụ giữ gìn sự công bằng tuyệt đối: "Vào trước, Ra trước". Tuy nhiên, thế giới thực không phải lúc nào cũng vận hành một cách bình đẳng.

Hãy tưởng tượng một phòng cấp cứu của bệnh viện: Một bệnh nhân bị đứt tay đến trước đang ngồi chờ xếp hàng, nhưng đột nhiên có một ca nhồi máu cơ tim được đưa vào. Bác sĩ không thể bắt ca nhồi máu cơ tim phải đợi theo luật FIFO. Hệ thống lúc này phải có khả năng "chen ngang", ưu tiên xử lý các tác vụ có mức độ khẩn cấp cao nhất. Đó là lý do Hàng đợi ưu tiên (Priority Queue) ra đời.

1. Hàng đợi ưu tiên (Priority Queue) là gì?

Priority Queue là một Kiểu dữ liệu trừu tượng (ADT) hoạt động giống hệt Queue thông thường (cũng có Enqueue và Dequeue), nhưng luật lấy dữ liệu bị thay đổi:

• Phần tử được Dequeue (lấy ra) không phải là phần tử nằm lâu nhất trong hàng đợi, mà là phần tử có mức độ ưu tiên cao nhất.

• Khi có nhiều phần tử cùng mức ưu tiên, chúng mới được xử lý theo luật FIFO.

Sự bế tắc của Mảng và Danh sách liên kết:

Nếu dùng Mảng hoặc Linked List để thiết kế Priority Queue, Hiếu sẽ gặp phải một nút thắt cổ chai về hiệu năng:

• Nếu dùng Mảng không sắp xếp: Thêm phần tử mất $O(1)$, nhưng mỗi lần lấy phần tử lớn nhất ra, ta phải quét toàn bộ mảng mất $O(n)$.

• Nếu dùng Mảng đã sắp xếp: Lấy phần tử lớn nhất mất $O(1)$ (lấy ở đuôi), nhưng mỗi lần chèn một phần tử mới vào đúng vị trí ưu tiên lại mất $O(n)$ (phải dịch chuyển mảng).

Để cân bằng cả hai thao tác Thêm và Lấy về tốc độ siêu tốc $O(\log n)$, ngành khoa học máy tính đã phát minh ra cấu trúc dữ liệu Heap.

2. Giải phẫu cấu trúc Heap (Min/Max Heap)

Heap thực chất là một Cây nhị phân hoàn chỉnh (Complete Binary Tree). Điều thú vị nhất ở Heap là nó không cần dùng đến các con trỏ Left, Right rời rạc như Linked List. Nó được ánh xạ trực tiếp và hoàn hảo lên một Mảng tuyến tính (Array).

Có 2 loại Heap cơ bản:

• Max Heap: Giá trị của Node cha luôn lớn hơn hoặc bằng giá trị của các Node con. Hệ quả: Nằm ở gốc của cây (vị trí đầu mảng) chắc chắn là phần tử lớn nhất.

• Min Heap: Giá trị của Node cha luôn nhỏ hơn hoặc bằng giá trị của các Node con. Gốc của cây là phần tử nhỏ nhất.

Công thức ánh xạ từ Cây xuống Mảng:

Nếu một Node đang nằm ở chỉ mục i trong mảng:

• Con trái (Left Child) nằm ở: 2i + 1

• Con phải (Right Child) nằm ở: 2i + 2

• Node cha (Parent) nằm ở: (i - 1) / 2 (chia nguyên)

Nhờ phép toán chỉ mục (index) đơn giản này, CPU cache truy xuất dữ liệu trên Heap với tốc độ cực kỳ khủng khiếp mà không gặp phải tình trạng Cache Miss.

3. Cơ chế Vun đống (Heapify)

Làm sao để duy trì luật lệ "Cha luôn lớn hơn Con" khi thêm hoặc xóa dữ liệu? Heap sử dụng hai cơ chế nổi nổi lên (Bubble Up) và chìm xuống (Bubble Down).

• Thêm phần tử (Push): Ta đẩy phần tử mới vào cuối mảng (đáy của cây). Sau đó so sánh nó với Node cha. Nếu nó lớn hơn cha, ta hoán đổi (Swap) vị trí của nó với cha. Quá trình "nổi lên" này (Sift-up) tiếp tục cho đến khi nó nhỏ hơn cha hoặc chạm đến đỉnh (Root).

• Lấy phần tử ưu tiên (Pop): Ta lấy phần tử trên đỉnh Root ra (đây luôn là giá trị lớn nhất). Để lấp chỗ trống, ta lấy phần tử ở cuối mảng đặt lên đỉnh Root. Lúc này luật Max Heap bị phá vỡ. Ta so sánh Root mới với 2 con của nó, chọn con lớn hơn và hoán đổi vị trí. Quá trình "chìm xuống" (Sift-down) này lặp lại cho đến khi Node đó lớn hơn cả 2 con của nó hoặc chạm đáy.

Độ cao của Cây nhị phân hoàn chỉnh luôn là $\log_2(n)$. Do đó, các thao tác di chuyển lên/xuống này chỉ tốn tối đa $O(\log n)$ bước.

4. Triển khai Max Heap bằng Golang

Dưới đây là mô hình một Max Heap thô được xây dựng bằng Slice trong Go:

Go

type MaxHeap struct {
    array []int
}

// Push thêm một phần tử vào Heap
func (h *MaxHeap) Push(key int) {
    h.array = append(h.array, key) // Thêm vào cuối mảng
    h.heapifyUp(len(h.array) - 1)  // Cho phần tử nổi lên đúng vị trí
}

// Pop lấy ra phần tử lớn nhất (nằm ở đỉnh)
func (h *MaxHeap) Pop() int {
    if len(h.array) == 0 {
        return -1 // Báo lỗi nếu Heap rỗng
    }
    
    maxVal := h.array[0]
    lastIndex := len(h.array) - 1
    
    // Đưa phần tử cuối cùng lên đỉnh mảng
    h.array[0] = h.array[lastIndex]
    h.array = h.array[:lastIndex] // Cắt bỏ phần tử cuối
    
    // Vun đống lại từ đỉnh cho chìm xuống
    h.heapifyDown(0)
    
    return maxVal
}

// Hàm đẩy phần tử nổi lên (Sift-up)
func (h *MaxHeap) heapifyUp(index int) {
    for index > 0 {
        parentIndex := (index - 1) / 2
        // Nếu con lớn hơn cha -> Đổi chỗ
        if h.array[index] > h.array[parentIndex] {
            h.array[index], h.array[parentIndex] = h.array[parentIndex], h.array[index]
            index = parentIndex
        } else {
            break // Đã đúng trật tự
        }
    }
}

// Hàm cho phần tử chìm xuống (Sift-down)
func (h *MaxHeap) heapifyDown(index int) {
    lastIndex := len(h.array) - 1
    for {
        leftChild := 2*index + 1
        rightChild := 2*index + 2
        largest := index

        // Tìm phần tử lớn nhất giữa Cha, Con trái và Con phải
        if leftChild <= lastIndex && h.array[leftChild] > h.array[largest] {
            largest = leftChild
        }
        if rightChild <= lastIndex && h.array[rightChild] > h.array[largest] {
            largest = rightChild
        }

        if largest != index {
            h.array[index], h.array[largest] = h.array[largest], h.array[index]
            index = largest // Tiếp tục chìm xuống
        } else {
            break // Đã ổn định
        }
    }
}

(Lưu ý: Trong thực tế dự án, Golang cung cấp sẵn package container/heap để biến bất kỳ Slice nào thành Heap thông qua việc implement interface, nhưng việc tự viết lõi thuật toán như trên là cách tốt nhất để hiểu sâu về cơ chế quản lý bộ nhớ).

5. Ứng dụng ở tầng Kiến trúc và Vận hành

Priority Queue / Heap là trái tim của những hệ thống ra quyết định và tối ưu hóa luồng công việc phức tạp:

• Hệ thống điều khiển tín hiệu Metro: Khi vận hành các tuyến Metro Line 1, hệ thống kiểm soát tín hiệu (Signaling System) phải liên tục nhận vô số bản tin từ các cảm biến trên đường ray. Một cảnh báo "Vượt quá tốc độ" (Priority 1) sẽ lập tức được đẩy lên đỉnh Heap để hệ thống kích hoạt phanh khẩn cấp, đẩy lùi các bản tin "Cập nhật nhiệt độ toa xe" (Priority 10) xuống phía dưới.

• Lập lịch CPU (OS Task Scheduling): Các hệ điều hành nhân Linux dùng cấu trúc tương tự Heap để theo dõi luồng nào (Thread) cần được cấp CPU tiếp theo dựa trên mức độ ưu tiên (Nice value).

• _Thuật toán tìm đường đi ngắn nhất (Dijkstra's / A):_* Khi Google Maps tìm đường đi, nó dùng một Min Heap để luôn luôn khám phá nút (ngã tư) có khoảng cách dự kiến ngắn nhất tiếp theo, nhờ đó bỏ qua được hàng triệu con đường vòng vèo vô ích.

Sự xuất hiện của Heap mở ra một khuôn mẫu thuật toán cực kỳ sắc bén mang tên "Top K Elements". Đây là dạng toán kinh điển nhất trong hệ thống phỏng vấn để xử lý các bảng xếp hạng từ những luồng dữ liệu vô tận.