⛰️ Heap & Priority Queue

Có một nhóm bài toán chỉ quan tâm đến “phần tử nhỏ nhất/lớn nhất hiện có” tại mỗi thời điểm, trong khi dữ liệu liên tục được thêm vào và lấy ra - ví dụ hàng đợi cấp cứu ở bệnh viện (bệnh nhân nặng nhất được khám trước, bất kể ai đến trước), hay việc lập lịch tiến trình trong hệ điều hành (tiến trình ưu tiên cao chạy trước). Dùng mảng đã sắp xếp thì tìm min/max cực nhanh (O(1)) nhưng chèn phần tử mới lại chậm (O(n)); dùng mảng chưa sắp xếp thì chèn nhanh nhưng tìm min/max lại phải quét cả mảng. Heap là cấu trúc dữ liệu dung hòa cả hai: cả chèn lẫn lấy ra phần tử nhỏ nhất/lớn nhất đều chỉ tốn O(log n).

Heap là gì?

Heap là một cây nhị phân gần đầy (các tầng trên đều lấp kín, tầng cuối lấp từ trái sang phải, không có “lỗ hổng” ở giữa), thỏa thêm một ràng buộc về thứ tự giá trị:

Min-heap: giá trị mỗi node luôn nhỏ hơn hoặc bằng giá trị hai con của nó → phần tử nhỏ nhất luôn nằm ở gốc.
Max-heap: giá trị mỗi node luôn lớn hơn hoặc bằng giá trị hai con của nó → phần tử lớn nhất luôn nằm ở gốc.

Chú ý: heap không phải một mảng đã sắp xếp hoàn toàn - nó chỉ đảm bảo quan hệ cha-con, không đảm bảo thứ tự giữa hai node anh em hay giữa các tầng khác nhau. Đây chính là điều giúp heap chèn/xóa nhanh hơn nhiều so với việc giữ một mảng luôn có thứ tự đầy đủ.

Vì sao dùng mảng để lưu heap?

Vì heap luôn là cây nhị phân gần đầy (không có lỗ hổng), ta có thể lưu nó trong một mảng phẳng mà không cần con trỏ: duyệt cây theo thứ tự từng tầng (level-order) rồi ghi giá trị lần lượt vào mảng. Quan hệ cha-con được suy ra thẳng từ chỉ số, không cần lưu thêm gì:

def left(i):   return 2 * i + 1
def right(i):  return 2 * i + 2
def parent(i): return (i - 1) // 2

Đây là cách biểu diễn cực kỳ gọn nhẹ - không tốn bộ nhớ cho con trỏ như cây thông thường, và tận dụng được tính cục bộ trong bộ nhớ của mảng (xem thêm ở trang Mảng).

Chèn phần tử: nổi dần lên (sift up)

Khi chèn một giá trị mới, ta đặt nó vào cuối mảng (vị trí lá tận cùng), sau đó liên tục so sánh với node cha: nếu vi phạm tính chất heap (ví dụ ở min-heap mà giá trị mới nhỏ hơn cha), hoán đổi hai node rồi tiếp tục “nổi” lên trên, cho tới khi tìm được chỗ đúng hoặc chạm gốc.

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)   # 1 "nổi" từ cuối mảng lên gần gốc
print(heap[0])            # 1 - luôn là phần tử nhỏ nhất (min-heap)

Vì cây có chiều cao O(log n), và mỗi bước “nổi” chỉ đi lên một tầng, số bước tối đa là chiều cao cây → chèn tốn O(log n).

Lấy phần tử gốc: chìm dần xuống (sift down)

Muốn lấy phần tử nhỏ nhất (gốc) ra khỏi heap mà không phá vỡ cấu trúc mảng-gần-đầy, ta không thể chỉ đơn giản xóa phần tử đầu mảng. Cách làm chuẩn:

Hoán đổi gốc với phần tử cuối cùng của mảng.
Xóa phần tử cuối (chính là gốc cũ) ra khỏi mảng.
Với phần tử mới ở vị trí gốc, liên tục so sánh với hai con, hoán đổi với con nhỏ hơn nếu vi phạm tính chất heap, “chìm” dần xuống cho tới đúng vị trí.

smallest = heapq.heappop(heap)   # O(log n): lấy ra và chỉnh lại heap

Cùng lý do như chèn, thao tác này cũng tốn O(log n).

Xây heap từ một mảng có sẵn - chỉ O(n)

Nếu đã có sẵn một mảng và muốn biến nó thành heap, cách “chèn từng phần tử một” tốn O(n log n) (n lần chèn, mỗi lần O(log n)). Nhưng có một thủ thuật nhanh hơn: áp dụng “chìm dần xuống” cho từng node không phải lá, theo thứ tự từ dưới lên trên - các node lá vốn đã tự động thỏa tính chất heap (không có con để so sánh) nên bỏ qua.

arr = [5, 2, 8, 1, 9, 3]
heapq.heapify(arr)   # biến arr thành min-heap tại chỗ

Trực giác vì sao cách này nhanh hơn: hầu hết node của một cây nhị phân nằm ở các tầng thấp gần lá, nơi việc “chìm xuống” chỉ tốn 1-2 bước; chỉ một số ít node ở gần gốc mới cần chìm sâu (O(log n) bước). Tính tổng công sức trên toàn bộ cây cho ra O(n) chứ không phải O(n log n).

Ứng dụng: bài toán Top-K

Đề bài: cho một mảng n phần tử, tìm k phần tử lớn nhất.

Cách đơn giản nhất - sắp xếp toàn bộ mảng rồi lấy k phần tử cuối - tốn O(n log n), “làm dư việc” vì đã sắp xếp luôn cả những phần tử không cần dùng đến. Cách hiệu quả hơn dùng min-heap kích thước cố định k:

def top_k_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)          # min-heap k phần tử đầu tiên

    for x in nums[k:]:
        if x > heap[0]:           # x lớn hơn phần tử nhỏ nhất đang giữ
            heapq.heapreplace(heap, x)   # loại phần tử nhỏ nhất, thêm x
    return heap

Ý tưởng: heap luôn giữ đúng k ứng viên tốt nhất tính đến thời điểm hiện tại, với phần tử nhỏ nhất trong số đó nằm ở gốc - nên chỉ cần so sánh phần tử mới với gốc để quyết định có đáng thay thế hay không. Độ phức tạp O(n log k): khi k nhỏ hơn nhiều so với n, cách này nhanh hơn hẳn O(n log n) của việc sắp xếp toàn bộ. Cách tiếp cận này cũng phù hợp với dữ liệu dạng luồng (stream) - liên tục có phần tử mới đến mà không cần giữ lại toàn bộ dữ liệu cũ.

Tóm tắt

Thao tác	Độ phức tạp	Cơ chế
Chèn (`push`)	O(log n)	Nổi dần lên (sift up)
Lấy gốc (`pop`)	O(log n)	Chìm dần xuống (sift down)
Xem gốc (`peek`)	O(1)	Gốc luôn ở đầu mảng
Xây từ mảng có sẵn	O(n)	Chìm dần xuống, từ dưới lên, bỏ qua lá